Solving linear systems using wavelet compression combined with Kronecker product approximation

Discrete wavelet transform approximation is an established means of approximating dense linear systems arising from discretization of differential and integral equations defined on a one-dimensional domain. For higher dimensional problems, approximation with a sum of Kronecker products has been shown to be effective in reducing storage and computational costs. We have combined these two approaches to enable solution of very large dense linear systems by an iterative technique using a Kronecker product approximation represented in a wavelet basis. Further approximation of the system using only a single Kronecker product provides an effective preconditioner for the system. Here we present our methods and illustrate them with some numerical examples. This technique has the potential for application in a range of areas including computational fluid dynamics, elasticity, lubrication theory and electrostatics. AMS subject classification 65F10, 65T60, 65F30 Judith M. Ford: This author was supported by EPSRC Postdoctoral Research Fellowship ref: GR/R95982/01. Current address: Royal Liverpool Children's NHS Trust, Liverpool, L12 2AP. Eugene E. Tyrtyshnikov: This author was supported by the Russian Fund of Basic Research (grant 02-01-00590) and Science Support Foundation.