The convergence rate and parallel performance of a 3D elliptic solver

• Autorzy: Lirkov I. , Vutov V.
• Języki publikacji: EN

Abstrakty

EN

It was shown that block-circulant preconditioners applied to a conjugate gradient method used to solve structured sparse linear systems arising from 2D or 3D elliptic problems have good numerical properties and a potential for high parallel efficiency. In this paper, the convergence rate and the parallel performance of a circulant block-factorization based preconditioner applied to a 3D problem are analyzed. A portable parallel code is developed based on Message Passing Interface (MPI) standards. The numerical tests performed on parallel computer systems demonstrate the level of efficiency of the algorithm developed.

Słowa kluczowe

EN

parallel algorithms; PCG method; preconditioner; circulant; performance

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Systems Science
• Rocznik: 2006
• Tom: Vol. 32, no 4
• Strony: 73--81
• Opis fizyczny: Bibliogr. 29 poz., wykr.

Twórcy

autor

Lirkov I.

autor

Vutov V.

• Bulgarian Academy of Sciences, Institute for Parallel Processing, Acad. G. Bonchev, 1113 Sofia, Bulgaria,

Bibliografia

• [1] Arbenz P., Margenov S., Vutov Y., Parallel MIC(O) Preconditioning of 3D Elliptic Problems Discretized by Rannacher-Turek Finite Elements, Comput. Math. Appl. (to appear).
• [2] Axelsson A.O.H., Neytcheva M.G., Supercomputers and numerical linear algebra, KLIN, Nijmegen, 1997.
• [3] Axelsson O., Iterative solution methods, Cambridge University Press, Cambridge, 1994.
• [4] Bencheva G., Margenov S., Starý J., Parallel PCG Solver for Nonconforming FE Problems: Overlapping of Communications and Computations. Large-Scale Scientific Computing, [in:] I. Lirkov, S. Margenov, and J. Waśniewski (eds.), Lecture notes in computer sciences, 3743, Springer Verlag, 2005, pp. 646-654.
• [5] Chan R.H., Chan T.F., Circulant preconditioners for elliptic problems, J. Num. Lin. Alg. Appl., 1, 1992, pp. 77-101.
• [6] Chan R.H., Strang G., Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Stat. Comp., 10, 1989, pp. 104-119.
• [7] Chan T.F., An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Stat. Comp., 9, 1988, pp. 766-771.
• [8] Davis P.J., Circulant matrices, John Wiley, New York, 1979.
• [9] Dongarra J., Duff I., Sorensen D., Vorst van der H., Numerical linear algebra for high-performance computers, SIAM Publication, Philadelphia, 1998.
• [10] Duff I.S., Meurant G.A., The effect of ordering on preconditioned conjugate gradients, BIT, 29, 1989, pp. 635-657.
• [11] Golub G.H., Van Loan C.F., Matrix Computations, Johns Hopkins Univ. Press, Baltimore, 2nd ed., 1989.
• [12] Hackbusch W., The frequency decomposition multi-grid method. 1. Application to anisotropic equations, Numer. Math., 56, 1989, pp. 219-245.
• [13] Holmgren S., Otto K., Iterative solution methods for block-tridiagonal systems of equations, SIAM J. Matr. Anal. Appl., 13, 1992, pp. 863-886.
• [14] Huckle T., Circulant and skewcirculant matrices for solving Toeplitz matrix problems, SIAM J. Matr. Anal. Appl., 13, 1992, pp. 767-777.
• [15] Huckle T., Some aspects of circulant preconditioners, SIAM J. Sci. Comput., 14, 1993, pp. 531-541.
• [16] Lirkov I., Margenov S., Parallel complexity of conjugate gradient method -with circulant preconditioners, Proc. Parcella’96, [in:] R. Volmar, W. Erhard, V. Jossifov (eds.), Mathematical research, 96, Akademie Verlag, Berlin, 1996, pp. 279-286.
• [17] Lirkov I., Margenov S., Parallel complexity of conjugate gradient method with circulant block-factorization preconditioners for 3D elliptic problems. Recent Advances in Numerical Methods and Applications, [in:] O.P. Iliev, M.S. Kaschiev, Bl. Sendov, P.V. Vassilevski (eds.), World Scientific, Singapore, 1999, pp. 482-490.
• [18] Lirkov I., Margenov S., Paprzycki M., Parallel conjugate gradient method with circulant block-factorization preconditioners for 3D elliptic problems, Proc. Ninth SIAM Conf. Parallel Processing for Scientific Computing, B. Hendrickson et. al. (eds.), SIAM, Philadelphia, 1999. files Marcin~l.pdf and Marcin~l.ps.
• [19] Lirkov I., Margenov S., Paprzycki M., Parallel performance of a 3D elliptic solver. Numerical Analysis and Its Applications H, [in:] L. Vulkov, J. Waśniewski, P. Yalamov (eds.), Lecture Notes in Computer Sciences, 1988, Springer Verlag, 2001, pp. 535-543.
• [20] Lirkov I., Margenov S., Paprzycki M., Owens R., A shared memory parallel implementation of block-circulant preconditioners. Large-Scale Scientific Computations of Engineering and Environmental problems, [in:] M. Griebel, O. Iliev, S. Margenov, P. Vassilevski (eds.), Notes on Numerical Fluid Mechanics, 62, Vieweg Verlag, Braunschweig, Germany, 1998, pp. 319-327.
• [21] Lirkov I., Margenov S., Vassilevski P., Circulant block-factorization preconditioners for elliptic problems, Computing, 53 (1), 1994, pp. 59-74.
• [22] Lirkov I., Margenov S., Zikatanov L., Circulant block-factorization preconditioning of anisotropic elliptic problems, Computing, 58 (3), 1997, pp. 245-258.
• [23] Loan van C., Computational frameworks for the fast Fourier transform, SIAM, Philadelphia, 1992.
• [24] Margenov S., Lirkov I., Preconditioned conjugate gradient iterative algorithms for transputer based systems, [in:] K. Boyanov (ed.), Parallel and distributed processing, Bulgarian Academy of Sciences, Sofia, 1993, pp. 406-415.
• [25] Margenov S.D., Vassilevski P.S., Algebraic multilevel preconditioning of anisotropic elliptic problems, SIAM J. Matrix Anal. Appl., 15 (5), 1994, pp. 1026-1037.
• [26] Saad Y., Schultz M.H., Data communication in parallel architectures, Parallel Comput., 11, 1989, pp. 131-150.
• [27] Snir M., Otto St., Huss-Lederman St., Walker D., Dongarra J., MPT. The Complete Reference, Scientific and engineering computation series. The MIT Press, Cambridge, Massachusetts, 1997. Second printing.
• [28] Strang G., A proposal for Toeplitz matrix calculations, Stud. Appl. Math., 74, 1986, pp. 171-176.
• [29] Zhu J., Solving partial differential equations on parallel computers, World Scientific, 1994.