LU factorization of non-standard forms and direct multiresolution solvers
algorithmsequations with pseudodifferential operatorlarge linear systemsLU factorizationmultigrid \(V\)-cyclenumerical resultsselfadjoint elliptic equationssparse matriceswavelets
Boundary value problems for second-order elliptic equations (35J25) Boundary value problems for PDEs with pseudodifferential operators (35S15) Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs (65N30)
This is an expository paper which tries to convince the reader that it may be advantageous to solve large linear systems of equations by transforming to a wavelet coordinate system, neglect then all matrix elements below a certain threshold \(\varepsilon\), perform specialized LU decomposition, forward and backward substitution on all wavelet scales, and transforming back. The algorithms for these decompositions and substitutions are explained in detail. The approach shows some similarity to a multigrid V-cycle -- but constitutes a direct solver (up to the neglections). Possible applications include selfadjoint elliptic equations or equations with pseudodifferential operator. The matrices obtained after discretization may be full. Operation count is mentioned to be \(O(n \ln(1/\varepsilon))\) with \(n\) the order of the system. This linear dependence of the number of operations on \(n\) is visible in the numerical results given (for matrices of orders from 128 to 2048). What does not become clear is a possible interplay between \(\varepsilon\), the number of vanishing moments of the wavelets, the half bandwidth considered, and \(n\). In the numerical examples, the accuracy reached is of the order \(\varepsilon\).
- A multiresolution strategy for numerical homogenization
- A multiresolution strategy for reduction of elliptic PDEs and eigenvalue problems
- Cholesky factorization of positive definite bi-infinite matrices
- Fast wavelet transforms and numerical algorithms I
- scientific article; zbMATH DE number 3976197 (Why is no real title available?)
- scientific article; zbMATH DE number 554500 (Why is no real title available?)
- scientific article; zbMATH DE number 1069193 (Why is no real title available?)
- Multiresolution Approximations and Wavelet Orthonormal Bases of L 2 (R)
- On Iterative Computation of Generalized Inverses and Associated Projections
- On the Numerical Properties of an Iterative Method for Computing the Moore–Penrose Generalized Inverse
- Propriétés des matrices ``bien localisées près de leur diagonale et quelques applications. (Properties of matrices ``well localized near the diagonal and some applications)
- Wavelet-Like Bases for the Fast Solution of Second-Kind Integral Equations
- A multiresolution strategy for reduction of elliptic PDEs and eigenvalue problems
- Fast spectral projection algorithms for density-matrix computations
- A fast direct solver for boundary integral equations in two dimensions
- Adaptive solution of partial differential equations in multiwavelet bases
- Samplets: construction and scattered data compression
- A fast, spectrally accurate homotopy based numerical method for solving nonlinear differential equations
- Operator-adapted wavelets for finite-element differential forms
- Fast homogenization algorithm based on asymptotic theory and multiscale schemes
- Kinetic energy-free Hartree-Fock equations: an integral formulation
- On A Recursive Schur Preconditioner For Iterative Solution Of A Class Of Dense Matrix Problems
- Fast algorithms for spectral collocation with non-periodic boundary conditions
- Simulation of a waveguide filter using wavelet-based numerical homogenization
- An explicitly-sparse representation for oscillatory kernels with wave atom-like functions
- An adaptive fast direct solver for boundary integral equations in two dimensions
- A fast wavelet block Jacobi method
- Sparse inverse Cholesky factorization of dense kernel matrices by greedy conditional selection
- The dimension weighted fast multipole method for scattered data approximation
- Sparse Cholesky factorization for solving nonlinear PDEs via Gaussian processes
- Explicit formulas for wavelet-homogenized coefficients of elliptic operators
- Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity
- Variants of algebraic wavelet-based multigrid methods: Application to shifted linear systems
This page was built for publication: LU factorization of non-standard forms and direct multiresolution solvers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1267269)
