M.Sc Thesis

M.Sc StudentBeliak Leonid
SubjectAdaptive Calculation of Variable Coefficients Elliptic
Differential Equations via
DepartmentDepartment of Computer Science
Supervisor PROF. Moshe Israeli (Deceased)


We propose a wavelet-based solver for strictly elliptic linear homogeneous PDE’s with non-constant coefficients of the form:

ΔU - b(x)U = f(x).

We consider efficient discretization and solution of differential equations with non-oscillatory behavior that has possibly localized regions with irregular structures. Similar to other discretization schemes for the solution of PDEs, in wavelet schemes we have to solve a system of linear equations in the wavelet coordinate basis. Preconditioned Conjugate gradient method is one of the most efficient methods to solve such a system. Using this method only a constant number of steps is needed to obtain a solution with a prescribed accuracy.

 We adaptively combine a sparse multiplication algorithm with an existing diagonally preconditioned conjugate gradient (CG) method based on wavelets. We use sparse data structures to take advantage of the O(Ns) complexity of the algorithm, where Ns is the number of significant coefficients (above a certain threshold) required for a given accuracy. In this work we show that the usage of sparse multiplication in wavelet space rather than in the original physical space can speed up by a factor of 20 the performance of a regular solver. Therefore, we present an algorithm and numerical results for adaptive multiplication scheme that can solve fast mentioned above equation. We explored how the accuracy of wavelet-based multiplication is affected by different input parameters of the algorithm. We extended and integrated sparse multiplication into a PDE solver. We also studied the relation between the performance of the solver and the parameters of the wavelet based sparse multiplication.