Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMultidimensional Phase Recovery and Interpolative Decomposition Butterfly Factorization
123
0
0.0
(
0
)
Added by
Haizhao Yang
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
The viscous flow of two immiscible fluids in a porous medium on the Darcy scale is governed by a system of nonlinear parabolic equations. If infinite mobility of one phase can be assumed (e.g. in soil layers in contact with the atmosphere) the system can be substituted by the scalar Richards model. Thus, the domain of the porous medium may be partitioned into disjoint subdomains with either the full two-phase or the simplified Richards model dynamics. Extending the one-model approach from [1, 2] we suggest coupling conditions for this hybrid model approach. Based on an Euler implicit discretisation, a linear iterative (-type) domain decomposition scheme is proposed, and proven to be convergent. The theoretical findings are verified by a comparative numerical study that in particular confirms the efficiency of the hybrid ansatz as compared to full two-phase model computations.
A third order real tensor is mapped to a special f-diagonal tensor by going through Discrete Fourier Transform (DFT), standard matrix SVD and inverse DFT. We call such an f-diagonal tensor an s-diagonal tensor. An f-diagonal tensor is an s-diagonal tensor if and only if it is mapped to itself in the above process. The third order tensor space is partitioned to orthogonal equivalence classes. Each orthogonal equivalence class has a unique s-diagonal tensor. Two s-diagonal tensors are equal if they are orthogonally equivalent. Third order tensors in an orthogonal equivalence class have the same tensor tubal rank and T-singular values. Four meaningful necessary conditions for s-diagonal tensors are presented. Then we present a set of sufficient and necessary conditions for s-diagonal tensors. Such conditions involve a special complex number. In the cases that the dimension of the third mode of the considered tensor is $2, 3$ and $4$, we present direct sufficient and necessary conditions which do not involve such a complex number.
New mathematical and numerical results are given for the coupling of the temperature equation of a fluid with Radiative Transfer: existence and uniqueness and a convergent monotone numerical scheme. The technique is shown to be feasible for studying the temperature of lake Leman heated by the sun and for the earth atmosphere to study the effects of greenhouse gases.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
