TY - JOUR
T1 - Fast construction of optimal circulant preconditioners for matrices from the fast dense matrix method
AU - CHAN, Raymond H.
AU - NG, Wing Fai
AU - SUN, Hai Wei
PY - 2000/3
Y1 - 2000/3
N2 - In this paper, we consider solving non-convolution type integral equations by the preconditioned conjugate gradient method. The fast dense matrix method is a fast multiplication scheme that provides a dense discretization matrix A approximating a given integral equation. The dense matrix A can be constructed in O(n) operations and requires only O(n) storage where n is the size of the matrix. Moreover, the matrix-vector multiplication Ax can be done in O(nlogn) operations. Thus if the conjugate gradient method is used to solve the discretized system, the cost per iteration is O(nlogn) operations. However, for some integral equations, such as the Fredholm integral equations of the first kind, the system will be ill-conditioned and therefore the convergence rate of the method will be slow. In these cases, preconditioning is required to speed up the convergence rate of the method. A good choice of preconditioner is the optimal circulant preconditioner which is the minimizer of \\C - A\\F in Frobenius norm over all circulant matrices C. It can be obtained by taking arithmetic averages of all the entries of A and therefore the cost of constructing the preconditioner is of O(n2) operations for general dense matrices. In this paper, we develop an O(nlogn) method of constructing the preconditioner for dense matrices A obtained from the fast dense matrix method. Application of these ideas to boundary integral equations from potential theory will be given. These equations are ill-conditioned whereas their optimal circulant preconditioned equations will be well-conditioned. The accuracy of the approximation A, the fast construction of the preconditioner and the fast convergence of the preconditioned systems will be illustrated by numerical examples.
AB - In this paper, we consider solving non-convolution type integral equations by the preconditioned conjugate gradient method. The fast dense matrix method is a fast multiplication scheme that provides a dense discretization matrix A approximating a given integral equation. The dense matrix A can be constructed in O(n) operations and requires only O(n) storage where n is the size of the matrix. Moreover, the matrix-vector multiplication Ax can be done in O(nlogn) operations. Thus if the conjugate gradient method is used to solve the discretized system, the cost per iteration is O(nlogn) operations. However, for some integral equations, such as the Fredholm integral equations of the first kind, the system will be ill-conditioned and therefore the convergence rate of the method will be slow. In these cases, preconditioning is required to speed up the convergence rate of the method. A good choice of preconditioner is the optimal circulant preconditioner which is the minimizer of \\C - A\\F in Frobenius norm over all circulant matrices C. It can be obtained by taking arithmetic averages of all the entries of A and therefore the cost of constructing the preconditioner is of O(n2) operations for general dense matrices. In this paper, we develop an O(nlogn) method of constructing the preconditioner for dense matrices A obtained from the fast dense matrix method. Application of these ideas to boundary integral equations from potential theory will be given. These equations are ill-conditioned whereas their optimal circulant preconditioned equations will be well-conditioned. The accuracy of the approximation A, the fast construction of the preconditioner and the fast convergence of the preconditioned systems will be illustrated by numerical examples.
KW - Circulant preconditioners
KW - Conjugate gradient method
KW - Integral equations
UR - http://www.scopus.com/inward/record.url?scp=0011922010&partnerID=8YFLogxK
U2 - 10.1023/A:1022310100575
DO - 10.1023/A:1022310100575
M3 - Journal Article (refereed)
AN - SCOPUS:0011922010
SN - 0006-3835
VL - 40
SP - 24
EP - 40
JO - BIT Numerical Mathematics
JF - BIT Numerical Mathematics
IS - 1
ER -