LU factorization of non-standard forms and direct multiresolution solvers
type: Item
instance of: scholarly article
title: LU factorization of non-standard forms and direct multiresolution solvers
zbMATH Open document ID: 0914.65017
author: K. Appert
published in: Applied and Computational Harmonic Analysis
publication date: 1998-12-03T00:00:00Z
review text: 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\).
reviewed by: Gisbert Stoyan
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65N30
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 35J25
Mathematics Subject Classification ID: 35S15
zbMATH DE Number: 1207277
zbMATH Keywords: wavelets
zbMATH Keywords: LU factorization
zbMATH Keywords: sparse matrices
zbMATH Keywords: large linear systems
zbMATH Keywords: algorithms
zbMATH Keywords: multigrid \(V\)-cycle
zbMATH Keywords: selfadjoint elliptic equations
zbMATH Keywords: equations with pseudodifferential operator
zbMATH Keywords: numerical results
MaRDI profile type: Publication
OpenAlex ID: W2054495283
cites work: Fast wavelet transforms and numerical algorithms I
cites work: Q4288302
cites work: Wavelet-Like Bases for the Fast Solution of Second-Kind Integral Equations
cites work: On Iterative Computation of Generalized Inverses and Associated Projections
cites work: On the Numerical Properties of an Iterative Method for Computing the Moore–Penrose Generalized Inverse
cites work: Q3740904
cites work: Multiresolution Approximations and Wavelet Orthonormal Bases of L 2 (R)
cites work: A multiresolution strategy for numerical homogenization
cites work: A multiresolution strategy for reduction of elliptic PDEs and eigenvalue problems
cites work: Q4358722
cites work: 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)
cites work: Cholesky factorization of positive definite bi-infinite matrices
DOI: 10.1006/ACHA.1997.0227
description: scientific article; zbMATH DE number 1207277