# A Recursive Skeletonization Factorization Based on Strong Admissibility

@article{Minden2017ARS, title={A Recursive Skeletonization Factorization Based on Strong Admissibility}, author={Victor Minden and Kenneth L. Ho and Anil Damle and Lexing Ying}, journal={Multiscale Model. Simul.}, year={2017}, volume={15}, pages={768-796} }

We introduce the strong recursive skeletonization factorization (RS-S), a new approximate matrix factorization based on recursive skeletonization for solving discretizations of linear integral equations associated with elliptic partial differential equations in two and three dimensions (and other matrices with similar hierarchical rank structure). Unlike previous skeletonization-based factorizations, RS-S uses a simple modification of skeletonization, strong skeletonization, which compresses… Expand

#### Figures, Tables, and Topics from this paper

#### 24 Citations

Interpolative Decomposition Butterfly Factorization

- Mathematics, Computer Science
- SIAM J. Sci. Comput.
- 2020

This paper introduces a "kernel-independent" interpolative decomposition butterfly factorization as a data-sparse approximation for matrices that satisfy a complementary low-rank property and is a general framework for nearly optimal fast matvec useful in a wide range of applications. Expand

INTERPOLATIVE DECOMPOSITION BUTTERFLY FACTORIZATION\ast

- 2020

\bfA \bfb \bfs \bft \bfr \bfa \bfc \bft . This paper introduces a ``kernel-independent"" interpolative decomposition butterfly factorization (IDBF) as a data-sparse approximation for matrices that… Expand

Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors

- Computer Science, Mathematics
- SIAM J. Sci. Comput.
- 2020

A hierarchical approximate factorization approach which addresses this issue by focusing on improving the accuracy on smooth eigenvectors by preserving the action of the factorized matrix on piecewise polynomial functions of the PDE domain. Expand

Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations

- Mathematics, Computer Science
- 2018

This work proposes a simple modification that can significantly improve the accuracy of the hierarchical interpolative factorization for elliptic partial differential equations at no additional asymptotic cost: applying a block Jacobi preconditioner before each level of skeletonization. Expand

Analytical Low-Rank Compression via Proxy Point Selection

- Computer Science, Mathematics
- SIAM J. Matrix Anal. Appl.
- 2020

This work provides an intuitive way of understanding the proxy point method and bridges the gap between this useful analytical strategy and practical low-rank approximations. Expand

Fast Spatial Gaussian Process Maximum Likelihood Estimation via Skeletonization Factorizations

- Computer Science, Mathematics
- Multiscale Model. Simul.
- 2017

A framework for unstructured observations in two spatial dimensions that allows for evaluation of the log-likelihood and its gradient in $\tilde O(n^{3/2})$ time under certain assumptions, where $n$ is the number of observations. Expand

Overlapping Domain Decomposition Preconditioner for Integral Equations

- Computer Science, Mathematics
- ArXiv
- 2021

A new preconditioner based on a novel overlapping domain decomposition that can be combined efficiently with fast direct solvers is introduced and it is observed that the condition number of the preconditionsed system is O(1), independent of the problem size. Expand

A hierarchical butterfly LU preconditioner for two-dimensional electromagnetic scattering problems involving open surfaces

- Mathematics, Computer Science
- J. Comput. Phys.
- 2020

The efficacy and accuracy of the proposed preconditioned iterative solver are demonstrated via its application to a broad range of scatterers involving up to 100 million unknowns. Expand

Simple non-extensive sparsification of the hierarchical matrices

- Computer Science, Mathematics
- Adv. Comput. Math.
- 2020

A non-extensive sparse factorization of the 2 ${\mathscr{H}}^{2}$ matrix is proposed that allows to substitute direct 𝓂 2 ${Â¬H}2$ solution with the solution of the system with an equivalent sparse matrix of the same size. Expand

FLAM: Fast Linear Algebra in MATLAB - Algorithms for Hierarchical Matrices

- Computer Science
- J. Open Source Softw.
- 2020

Many large matrices in science and engineering possess a special hierarchical low-rank structure that enables fast multiplication and inversion, among other fundamental operations. Such matrices… Expand

#### References

SHOWING 1-10 OF 41 REFERENCES

A Fast Direct Solver for Structured Linear Systems by Recursive Skeletonization

- Mathematics, Computer Science
- SIAM J. Sci. Comput.
- 2012

Using the recently developed interpolative decomposition of a low-rank matrix in a recursive manner, an approximation of the original matrix is embedded into a larger but highly structured sparse one that allows fast factorization and application of the inverse. Expand

A Technique for Updating Hierarchical Skeletonization-Based Factorizations of Integral Operators

- Mathematics, Computer Science
- Multiscale Model. Simul.
- 2016

A method for updating certain hierarchical factorizations for solving linear integral equations with elliptic kernels and hierarchical interpolative factorization and demonstrates scaling results for a number of different two-dimensional (2D) problem setups. Expand

Superfast Multifrontal Method for Large Structured Linear Systems of Equations

- Mathematics, Computer Science
- SIAM J. Matrix Anal. Appl.
- 2009

A fast direct solver for large discretized linear systems using the supernodal multifrontal method together with low-rank approximations, especially suitable for large sparse problems and also has natural adaptability to parallel computations and great potential to provide effective preconditioners. Expand

Fast Spatial Gaussian Process Maximum Likelihood Estimation via Skeletonization Factorizations

- Computer Science, Mathematics
- Multiscale Model. Simul.
- 2017

A framework for unstructured observations in two spatial dimensions that allows for evaluation of the log-likelihood and its gradient in $\tilde O(n^{3/2})$ time under certain assumptions, where $n$ is the number of observations. Expand

An O(N) Direct Solver for Integral Equations on the Plane

- Mathematics
- 2013

An efficient direct solver for volume integral equations with O(N) complexity for a broad range of problems is presented. The solver relies on hierarchical compression of the discretized integral… Expand

A Fast Solver for HSS Representations via Sparse Matrices

- Mathematics, Computer Science
- SIAM J. Matrix Anal. Appl.
- 2006

A fast direct solver for certain classes of dense structured linear systems that works by first converting the given dense system to a larger system of block sparse equations and then uses standard sparse direct solvers. Expand

The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems

- Mathematics, Computer Science
- SIAM J. Sci. Comput.
- 2017

A preconditioner with broad applicability and with cost $\mathcal{O}(N)$ for dense matrices, when the matrix is given by a smooth kernel, which ensures that the sparsity pattern of the extended sparse matrix is preserved throughout the elimination, resulting in a very efficient algorithm. Expand

Data-sparse Approximation by Adaptive ℋ2-Matrices

- Mathematics, Computer Science
- Computing
- 2002

The basic ideas of ℋ- andℋ2-matrices are introduced and an algorithm that adaptively computes approximations of general matrices in the latter format is presented. Expand

A direct solver with O(N) complexity for integral equations on one-dimensional domains

- Mathematics
- 2011

An algorithm for the direct inversion of the linear systems arising from Nyström discretization of integral equations on one-dimensional domains is described. The method typically has O(N) complexity… Expand

"Compress and eliminate" solver for symmetric positive definite sparse matrices

- Mathematics, Computer Science
- SIAM J. Sci. Comput.
- 2018

It is shown that the resulting factorization can be used as an efficient preconditioner and compare the proposed approach with state-of-art direct and iterative solvers. Expand