This article presents two new algebraic algorithms to perform fast matrix-vector product for $N$-body problems in $d$ dimensions, namely nHODLR$d$D (nested algorithm) and s-nHODLR$d$D (semi-nested or partially nested algorithm). The nHODLR$d$D and s-nHODLR$d$D algorithms are the nested and semi-nested version of our previously proposed fast algorithm, the hierarchically off-diagonal low-rank matrix in $d$ dimensions (HODLR$d$D), respectively, where the admissible clusters are the certain far-field and the vertex-sharing clusters. We rely on algebraic low-rank approximation techniques (ACA and NCA) and develop both algorithms in a black-box (kernel-independent) fashion. The initialization time of the proposed hierarchical structures scales quasi-linearly. Using the nHODLR$d$D and s-nHODLR$d$D hierarchical structures, one can perform the multiplication of a dense matrix (arising out of $N$-body problems) with a vector that scales as $\mathcal{O}(pN)$ and $\mathcal{O}(pN \log(N))$, respectively, where $p$ grows at most poly logarithmically with $N$. The numerical results in $2$D and $3$D $(d=2,3)$ show that the proposed nHODLR$d$D algorithm is competitive to the algebraic Fast Multipole Method in $d$ dimensions with respect to the matrix-vector product time and space complexity. The C++ implementation with OpenMP parallelization of the proposed algorithms is available at \url{//github.com/riteshkhan/nHODLRdD/}.
相關內容
We develop a method to compute the $H^2$-conforming finite element approximation to planar fourth order elliptic problems without having to implement $C^1$ elements. The algorithm consists of replacing the original $H^2$-conforming scheme with pre-processing and post-processing steps that require only an $H^1$-conforming Poisson type solve and an inner Stokes-like problem that again only requires at most $H^1$-conformity. We then demonstrate the method applied to the Morgan-Scott elements with three numerical examples.
Iterative sketching and sketch-and-precondition are randomized algorithms used for solving overdetermined linear least-squares problems. When implemented in exact arithmetic, these algorithms produce high-accuracy solutions to least-squares problems faster than standard direct methods based on QR factorization. Recently, Meier, Nakatsukasa, Townsend, and Webb demonstrated numerical instabilities in a version of sketch-and-precondition in floating point arithmetic (arXiv:2302.07202). The work of Meier et al. raises the question: Is there a randomized least-squares solver that is both fast and stable? This paper resolves this question in the affirmative by proving that iterative sketching, appropriately implemented, is forward stable. Numerical experiments confirm the theoretical findings, demonstrating that iterative sketching is stable and faster than QR-based solvers for large problem instances.
We study versions of Hilbert's projective metric for spaces of integrable functions of bounded growth. These metrics originate from cones which are relaxations of the cone of all non-negative functions, in the sense that they include all functions having non-negative integral values when multiplied with certain test functions. We show that kernel integral operators are contractions with respect to suitable specifications of such metrics even for kernels which are not bounded away from zero, provided that the decay to zero of the kernel is controlled. As an application to entropic optimal transport, we show exponential convergence of Sinkhorn's algorithm in settings where the marginal distributions have sufficiently light tails compared to the growth of the cost function.
Most sequence sketching methods work by selecting specific $k$-mers from sequences so that the similarity between two sequences can be estimated using only the sketches. Estimating sequence similarity is much faster using sketches than using sequence alignment, hence sketching methods are used to reduce the computational requirements of computational biology software packages. Applications using sketches often rely on properties of the $k$-mer selection procedure to ensure that using a sketch does not degrade the quality of the results compared with using sequence alignment. In particular the window guarantee ensures that no long region of the sequence goes unrepresented in the sketch. A sketching method with a window guarantee corresponds to a Decycling Set, aka an unavoidable sets of $k$-mers. Any long enough sequence must contain a $k$-mer from any decycling set (hence, it is unavoidable). Conversely, a decycling set defines a sketching method by selecting the $k$-mers from the set. Although current methods use one of a small number of sketching method families, the space of decycling sets is much larger, and largely unexplored. Finding decycling sets with desirable characteristics is a promising approach to discovering new sketching methods with improved performance (e.g., with small window guarantee). The Minimum Decycling Sets (MDSs) are of particular interest because of their small size. Only two algorithms, by Mykkeltveit and Champarnaud, are known to generate two particular MDSs, although there is a vast number of alternative MDSs. We provide a simple method that allows one to explore the space of MDSs and to find sets optimized for desirable properties. We give evidence that the Mykkeltveit sets are close to optimal regarding one particular property, the remaining path length.
In this paper, we develop reliable a posteriori error estimates for numerical approximations of scalar hyperbolic conservation laws in one space dimension. Our methods have no inherent small-data limitations and are a step towards error control of numerical schemes for systems. We are careful not to appeal to the Kruzhkov theory for scalar conservation laws. Instead, we derive novel quantitative stability estimates that extend the theory of shifts, and in particular, the framework for proving stability first developed by the second author and Vasseur. This is the first time this methodology has been used for quantitative estimates. We work entirely within the context of the theory of shifts and $a$-contraction, techniques which adapt well to systems. In fact, the stability framework by the second author and Vasseur has itself recently been pushed to systems [Chen-Krupa-Vasseur. Uniqueness and weak-BV stability for $2\times 2$ conservation laws. Arch. Ration. Mech. Anal., 246(1):299--332, 2022]. Our theoretical findings are complemented by a numerical implementation in MATLAB and numerical experiments.
We describe a quantum algorithm based on an interior point method for solving a linear program with $n$ inequality constraints on $d$ variables. The algorithm explicitly returns a feasible solution that is $\epsilon$-close to optimal, and runs in time $\sqrt{n}\, \mathrm{poly}(d,\log(n),\log(1/\varepsilon))$ which is sublinear for tall linear programs (i.e., $n \gg d$). Our algorithm speeds up the Newton step in the state-of-the-art interior point method of Lee and Sidford [FOCS '14]. This requires us to efficiently approximate the Hessian and gradient of the barrier function, and these are our main contributions. To approximate the Hessian, we describe a quantum algorithm for the spectral approximation of $A^T A$ for a tall matrix $A \in \mathbb R^{n \times d}$. The algorithm uses leverage score sampling in combination with Grover search, and returns a $\delta$-approximation by making $O(\sqrt{nd}/\delta)$ row queries to $A$. This generalizes an earlier quantum speedup for graph sparsification by Apers and de Wolf [FOCS '20]. To approximate the gradient, we use a recent quantum algorithm for multivariate mean estimation by Cornelissen, Hamoudi and Jerbi [STOC '22]. While a naive implementation introduces a dependence on the condition number of the Hessian, we avoid this by pre-conditioning our random variable using our quantum algorithm for spectral approximation.
Thanks to the singularity of the solution of linear subdiffusion problems, most time-stepping methods on uniform meshes can result in $O(\tau)$ accuracy where $\tau$ denotes the time step. The present work aims to discover the reason why some type of Crank-Nicolson schemes (the averaging Crank-Nicolson scheme) for the subdiffusion can only yield $O(\tau^\alpha)$$(\alpha<1)$ accuracy, which is much lower than the desired. The existing well developed error analysis for the subdiffusion, which has been successfully applied to many time-stepping methods such as the fractional BDF-$p (1\leq p\leq 6)$, all requires singular points be out of the path of contour integrals involved. The averaging Crank-Nicolson scheme in this work is quite natural but fails to meet this requirement. By resorting to the residue theorem, some novel sharp error analysis is developed in this study, upon which correction methods are further designed to obtain the optimal $O(\tau^2)$ accuracy. All results are verified by numerical tests.
We study integration and $L^2$-approximation of functions of infinitely many variables in the following setting: The underlying function space is the countably infinite tensor product of univariate Hermite spaces and the probability measure is the corresponding product of the standard normal distribution. The maximal domain of the functions from this tensor product space is necessarily a proper subset of the sequence space $\mathbb{R}^\mathbb{N}$. We establish upper and lower bounds for the minimal worst case errors under general assumptions; these bounds do match for tensor products of well-studied Hermite spaces of functions with finite or with infinite smoothness. In the proofs we employ embedding results, and the upper bounds are attained constructively with the help of multivariate decomposition methods.
Quantifying the difference between two probability density functions, $p$ and $q$, using available data, is a fundamental problem in Statistics and Machine Learning. A usual approach for addressing this problem is the likelihood-ratio estimation (LRE) between $p$ and $q$, which -- to our best knowledge -- has been investigated mainly for the offline case. This paper contributes by introducing a new framework for online non-parametric LRE (OLRE) for the setting where pairs of iid observations $(x_t \sim p, x'_t \sim q)$ are observed over time. The non-parametric nature of our approach has the advantage of being agnostic to the forms of $p$ and $q$. Moreover, we capitalize on the recent advances in Kernel Methods and functional minimization to develop an estimator that can be efficiently updated online. We provide theoretical guarantees for the performance of the OLRE method along with empirical validation in synthetic experiments.
We propose a new framework for the simultaneous inference of monotone and smoothly time-varying functions under complex temporal dynamics utilizing the monotone rearrangement and the nonparametric estimation. We capitalize the Gaussian approximation for the nonparametric monotone estimator and construct the asymptotically correct simultaneous confidence bands (SCBs) by carefully designed bootstrap methods. We investigate two general and practical scenarios. The first is the simultaneous inference of monotone smooth trends from moderately high-dimensional time series, and the proposed algorithm has been employed for the joint inference of temperature curves from multiple areas. Specifically, most existing methods are designed for a single monotone smooth trend. In such cases, our proposed SCB empirically exhibits the narrowest width among existing approaches while maintaining confidence levels, and has been used for testing several hypotheses tailored to global warming. The second scenario involves simultaneous inference of monotone and smoothly time-varying regression coefficients in time-varying coefficient linear models. The proposed algorithm has been utilized for testing the impact of sunshine duration on temperature which is believed to be increasing by the increasingly severe greenhouse effect. The validity of the proposed methods has been justified in theory as well as by extensive simulations.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191