Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInterpolative Decomposition Butterfly Factorization
116
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
This paper introduces a kernel-independent interpolative decomposition butterfly factorization (IDBF) as a data-sparse approximation for matrices that satisfy a complementary low-rank property. The IDBF can be constructed in $O(Nlog N)$ operations for an $Ntimes N$ matrix via hierarchical interpolative decompositions (IDs), if matrix entries can be sampled individually and each sample takes $O(1)$ operations. The resulting factorization is a product of $O(log N)$ sparse matrices, each with $O(N)$ non-zero entries. Hence, it can be applied to a vector rapidly in $O(Nlog N)$ operations. IDBF is a general framework for nearly optimal fast matvec useful in a wide range of applications, e.g., special function transformation, Fourier integral operators, high-frequency wave computation. Numerical results are provided to demonstrate the effectiveness of the butterfly factorization and its construction algorithms.
rate research
Read More
This paper focuses on the fast evaluation of the matvec $g=Kf$ for $Kin mathbb{C}^{Ntimes N}$, which is the discretization of a multidimensional oscillatory integral transform $g(x) = int K(x,xi) f(xi)dxi$ with a kernel function $K(x,xi)=e^{2pii Phi(x,xi)}$, where $Phi(x,xi)$ is a piecewise smooth phase function with $x$ and $xi$ in $mathbb{R}^d$ for $d=2$ or $3$. A new framework is introduced to compute $Kf$ with $O(Nlog N)$ time and memory complexity in the case that only indirect access to the phase function $Phi$ is available. This framework consists of two main steps: 1) an $O(Nlog N)$ algorithm for recovering the multidimensional phase function $Phi$ from indirect access is proposed; 2) a multidimensional interpolative decomposition butterfly factorization (MIDBF) is designed to evaluate the matvec $Kf$ with an $O(Nlog N)$ complexity once $Phi$ is available. Numerical results are provided to demonstrate the effectiveness of the proposed framework.
We describe an algorithm for the application of the forward and inverse spherical harmonic transforms. It is based on a new method for rapidly computing the forward and inverse associated Legendre transforms by hierarchically applying the interpolative decomposition butterfly factorization (IDBF). Experimental evidence suggests that the total running time of our method -- including all necessary precomputations -- is $mathcal{O}(N^2 log^3(N))$, where $N$ is the order of the transform. This is nearly asymptotically optimal. Moreover, unlike existing algorithms which are asymptotically optimal or nearly so, the constant in the running time of our algorithm is small enough to make it competitive with state-of-the-art $mathcal{O}left(N^3right)$ methods at relatively small values of $N$. Numerical results are provided to demonstrate the effectiveness and numerical stability of the new framework.
Multiresolution Matrix Factorization (MMF) was recently introduced as an alternative to the dominant low-rank paradigm in order to capture structure in matrices at multiple different scales. Using ideas from multiresolution analysis (MRA), MMF teased out hierarchical structure in symmetric matrices by constructing a sequence of wavelet bases. While effective for such matrices, there is plenty of data that is more naturally represented as nonsymmetric matrices (e.g. directed graphs), but nevertheless has similar hierarchical structure. In this paper, we explore techniques for extending MMF to any square matrix. We validate our approach on numerous matrix compression tasks, demonstrating its efficacy compared to low-rank methods. Moreover, we also show that a combined low-rank and MMF approach, which amounts to removing a small global-scale component of the matrix and then extracting hierarchical structure from the residual, is even more effective than each of the two complementary methods for matrix compression.
The fast assembling of stiffness and mass matrices is a key issue in isogeometric analysis, particularly if the spline degree is increased. We present two algorithms based on the idea of sum factorization, one for matrix assembling and one for matrix-free methods, and study the behavior of their computational complexity in terms of the spline order $p$. Opposed to the standard approach, these algorithms do not apply the idea element-wise, but globally or on macro-elements. If this approach is applied to Gauss quadrature, the computational complexity grows as $p^{d+2}$ instead of $p^{2d+1}$ as previously achieved.
The accurate approximation of high-dimensional functions is an essential task in uncertainty quantification and many other fields. We propose a new function approximation scheme based on a spectral extension of the tensor-train (TT) decomposition. We first define a functional version of the TT decomposition and analyze its properties. We obtain results on the convergence of the decomposition, revealing links between the regularity of the function, the dimension of the input space, and the TT ranks. We also show that the regularity of the target function is preserved by the univariate functions (i.e., the cores) comprising the functional TT decomposition. This result motivates an approximation scheme employing polynomial approximations of the cores. For functions with appropriate regularity, the resulting textit{spectral tensor-train decomposition} combines the favorable dimension-scaling of the TT decomposition with the spectral convergence rate of polynomial approximations, yielding efficient and accurate surrogates for high-dimensional functions. To construct these decompositions, we use the sampling algorithm texttt{TT-DMRG-cross} to obtain the TT decomposition of tensors resulting from suitable discretizations of the target function. We assess the performance of the method on a range of numerical examples: a modifed set of Genz functions with dimension up to $100$, and functions with mixed Fourier modes or with local features. We observe significant improvements in performance over an anisotropic adaptive Smolyak approach. The method is also used to approximate the solution of an elliptic PDE with random input data. The open source software and examples presented in this work are available online.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
