IJPAM: Volume 47, No. 4 (2008)


Amir Averbuch$^1$, Leonid Beliak$^2$, Moshe Israeli$^3$
$^1$School of Mathematical Sciences
Faculty of Exact Sciences
Tel Aviv University
P.O. Box 39040, Ramat Aviv, Tel Aviv, 69978, ISRAEL
$^{2,3}$Faculty of Computer Science
Technion - Israel Institute of Technology
Haifa, 32000, ISRAEL

Abstract.We propose a solver for 1-D strictly elliptic linear PDE's with non-constant coefficients of the form $\Delta U - b(x)U = f(x)$. We combine a sparse multiplication algorithm with a diagonally preconditioned conjugate gradient (CG) method. We use sparse data structures to take advantage of the $O(N_s)$ complexity of the algorithm, where $N_s$ is the number of significant coefficients (i.e. above a certain threshold) required for a given accuracy.

We show that the usage of a sparse multiplication in wavelet space rather than in the original physical space can speed up the performance of the sparse solver by a factor of 20. We present an algorithm and numerical results for an adaptive multiplication scheme that can rapidly solve the equation above. We explore, in detail, how the accuracy of the wavelet-based multiplication is affected by different input parameters for the algorithm. We integrated a sparse multiplication into the PDE solver. The relation between the performance of the solver and the parameters of the wavelet based sparse multiplication is also studied. This integration allowed us to extend the fast adaptive algorithms to achieve numerical solutions of linear non-constant coefficient differential equations. One-dimensional numerical examples for using stand alone sparse multiplication and for the differential equations solver are presented. This work, which is based on [#!a1!#], extends it.

Received: August 20, 2008

AMS Subject Classification: 35J15

Key Words and Phrases: solver for 1-D strictly elliptic linear PDE, wavelet space, sparse data structures, numerical results for an adaptive multiplication scheme

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2008
Volume: 47
Issue: 4