Circulant block-factorization preconditioners for elliptic problems. (English) Zbl 0810.65039
Authors’ summary: New circulant block-factorization preconditioners are introduced and studied. The general approach is first formulated for the case of block tridiagonal sparse matrices. Then estimates of the relative condition number for a model Dirichlet boundary value problem are derived.
In the case of \(y\)-periodic problems the circulant block-factorization preconditioner is shown to give an optimal convergence rate. Finally, using a proper imbedding of the original Dirichlet boundary value problem to a \(y\)-periodic one a preconditioner of optimal convergence rate for the general case is obtained.
The total computational cost of the preconditioner is \(O(N \log N)\) (based on FFT), where \(N\) is the number of unknowns. That is, the algorithm is nearly optimal. Various numerical tests that demonstrate the features of the circulant block-factorization preconditioners are presented.
In the case of \(y\)-periodic problems the circulant block-factorization preconditioner is shown to give an optimal convergence rate. Finally, using a proper imbedding of the original Dirichlet boundary value problem to a \(y\)-periodic one a preconditioner of optimal convergence rate for the general case is obtained.
The total computational cost of the preconditioner is \(O(N \log N)\) (based on FFT), where \(N\) is the number of unknowns. That is, the algorithm is nearly optimal. Various numerical tests that demonstrate the features of the circulant block-factorization preconditioners are presented.
Reviewer: J.Zítko (Praha)
MSC:
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 65F10 | Iterative numerical methods for linear systems |
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
| 35J25 | Boundary value problems for second-order elliptic equations |
| 65N22 | Numerical solution of discretized equations for boundary value problems involving PDEs |
Keywords:
numerical examples; circulant block-factorization preconditioners; block tridiagonal sparse matrices; condition number; Dirichlet boundary value problem; optimal convergence rateReferences:
| [1] | Axelsson, O.: A survey of vectorizable preconditioning methods for large scale finite element matrices. In: Colloquium topics in applied numerical analysis, (Verwer, J. G., ed.), pp. 21–47. Syllabus 4, Center of Mathematics and Informatics (CMI), Amsterdam 1983. |
| [2] | Axelsson, O., Barker, V. A.: Finite element solution of boundary value problems: theory and computations. Orlando: Academic Press 1983. · Zbl 0981.65130 |
| [3] | Axelsson, O., Brinkkemper, S., Il’in, V. P.: On some versions of incomplete block-matrix factorization methods, Lin Alg. Appl.38, 3–15 (1984). · Zbl 0548.65016 · doi:10.1016/0024-3795(84)90200-3 |
| [4] | Axelsson, O., Polman, B.: On approximate factorization methods for block-matrices suitable for vector and parallel processors. Lin. Alg. Appl.77, 3–26 (1986). · Zbl 0587.65013 · doi:10.1016/0024-3795(86)90159-X |
| [5] | Axelsson, O., Eijkhout, V. L.: Robust vectorizable preconditioners for three-dimensional elliptic difference equations with anisotropy. Algorithms and applications on vector and parallel computers, (te Riele, H. J. J., Dekker, Th. J., van der Vorst, H., eds.), pp. 279–306. Amsterdam: North-Holland 1987. |
| [6] | Bank, R. E.: Marching algorithms for elliptic boundary value problems. II: The variable coefficient case. SIAM J. Numer. Anal.14, 950–970 (1977). · Zbl 0382.65052 · doi:10.1137/0714064 |
| [7] | Chan, R. H., Chan, T. F.: Circulant preconditioners for elliptic problems. J. Numerical Lin. Alg. Appl.1, 77–101 (1992). |
| [8] | Chan, T. F., Mathew, T. P.: The interface probing technique in domain decomposition. SIAM J. Matr. Anal. Appl.13, 212–238 (1992). · Zbl 0754.65099 · doi:10.1137/0613018 |
| [9] | Chan, T. F., Vassilevski, P. S.: A framework for block-ILU factorizations using block-size reduction. Math. Comp. (in press). · Zbl 0819.65018 |
| [10] | Concus, P., Golub, G. H., Meurant, G.: Block preconditioning for the conjugate gradient method. SIAM J. Sci. Stat. Comput.6, 220–252 (1985). · Zbl 0556.65022 · doi:10.1137/0906018 |
| [11] | D’yakonov, E. G.: On an iterative method for the solution of finite difference equations. Dokl. Acad. Nauk SSSR138, 522–525 (1961). |
| [12] | Davis, P. J.: Circulant matrices. New York: John Wiley 1979. · Zbl 0418.15017 |
| [13] | Golub, G. H., van Loan, C. F.: Matrix computations, 2nd edn. Baltimore: Johns Hopkins Univ. Press 1989. · Zbl 0733.65016 |
| [14] | Gunn, J. E.: The solution of difference equations by semi-explicit iterative techniques. SIAM J. Num. Anal.2, 24–45 (1965). · Zbl 0137.33301 |
| [15] | Gustafsson, I.: A class of first-order factorization methods. BIT18, 142–156 (1978). · Zbl 0386.65006 · doi:10.1007/BF01931691 |
| [16] | Holmgren, S., Otto, K.: Iterative solution methods for block-tridiagonal systems of equations. SIAM J. Matr. Anal. Appl.13, 863–886 (1992). · Zbl 0760.65032 · doi:10.1137/0613053 |
| [17] | Huckle, T.: Some aspects of circulant preconditioners. SIAM J. Sci. Comput.14, 531–541 (1993). · Zbl 0783.65044 · doi:10.1137/0914034 |
| [18] | Huckle, T.: Circulant and skewcirculant matrices for solving Toeplitz matrix problems. SIAM J. Matr. Anal. Appl.13, 767–777 (1992). · Zbl 0756.65047 · doi:10.1137/0613048 |
| [19] | Kettler, R.: Analysis and computations of relaxed schemes in robust multigrid and preconditioned conjugate gradient methods. In: Multigrid methods, Proceedings (Hackbusch, W., Trottenberg, U., eds.), pp. 502–534. Berlin Heidelberg New York Tokyo: Springer 1982 (Lecture Notes in Mathematics, Vol. 960). · Zbl 0505.65048 |
| [20] | van Loan, C.: Computational frameworks for the fast Fourier transform. Philadelphia: SIAM 1992. · Zbl 0757.65154 |
| [21] | Margenov, S. D., Lirkov, I. T.: Preconditioned conjugate gradient iterative algorithms for transputer based systems. In: Parallel and distributed processing (Boyanov, K., ed.), pp. 406–415. Sofia: BAS 1993. |
| [22] | Meurant, G.: The block-preconditioned conjugate gradient method on vector computers. BIT24, 623–633 (1984). · Zbl 0556.65023 · doi:10.1007/BF01934919 |
| [23] | Meurant, G.: A review on the inverse of symmetric tridiagonal and block tridiagonal matrices. SIAM J. Matr. Anal. Appl.13, 707–728 (1992). · Zbl 0754.65029 · doi:10.1137/0613045 |
| [24] | Strang, G.: A proposal for Toeplitz matrix calculations. Stud. Appl. Math.74, 171–176 (1986). · Zbl 0621.65025 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
