Stability and spectral properties of some incomplete block factorizations. (English) Zbl 0756.65031
The paper concerns preconditioning by incomplete block factorization of the type \(PD^{-1}P^ T\) where \(D\) is a block diagonal and \(P\) is a twisted block triangular matrix. More precisely, \(P\) has nonzero blocks only in the diagonal positions and the positions \((i,i-1)\) for \(i\leq k\) and \((i,i+1)\) for \(k\leq i\), where \(k\) is a parameter.
For this type of incomplete factorization, results concerning stability of factorization, error due to incomplete factorization and spectral characterization of the preconditioning effect are presented and the new type of factorization is compared with the standard incomplete block \(LD^{-1}L^ T\) factorization.
The main reason for introducing this new type of incomplete factorization is the possibility of parallel processing. For a two processor parallel computer the speed up of about 2 is reached in the presented numerical experiments.
For this type of incomplete factorization, results concerning stability of factorization, error due to incomplete factorization and spectral characterization of the preconditioning effect are presented and the new type of factorization is compared with the standard incomplete block \(LD^{-1}L^ T\) factorization.
The main reason for introducing this new type of incomplete factorization is the possibility of parallel processing. For a two processor parallel computer the speed up of about 2 is reached in the presented numerical experiments.
Reviewer: R.Blaheta (Ostrava)
MSC:
65F05 | Direct numerical methods for linear systems and matrix inversion |
65F35 | Numerical computation of matrix norms, conditioning, scaling |
65Y05 | Parallel numerical computation |
65F10 | Iterative numerical methods for linear systems |
Keywords:
twisted triangular factors; preconditioned conjugate gradient method; preconditioning; incomplete block factorization; stability; parallel processing; numerical experimentsReferences:
[1] | O. Axelsson A survey of preconditioned iterative methods for linear systems of algebraic equations, BIT 25 (1985) 166–187. · Zbl 0566.65017 · doi:10.1007/BF01934996 |
[2] | D. Bini, M. Capovani, O. Menchi,Metodi numerici per l’algebra lineare, (1988) Zanichelli. · Zbl 0697.65009 |
[3] | L. Brugnano,Incomplete twisted block factorization: Analysis of stability and its use in a parallel PCG algorithm, Rapporto interno I.R.M.A.-CNR, No. 2/89, c/o Dipartimento di Matematica, Università degli Studi di Bari (Italy). |
[4] | P. Concus, G. H. Golub, G. Meurant,Block preconditioning for the conjugated gradient method, SIAM J. Sci. Statist. Comput. 6, 1, 1985, 220–252. · Zbl 0556.65022 · doi:10.1137/0906018 |
[5] | P. Concus, G. Meurant,On computing the INV block preconditionings for the conjugated gradient method, BIT 26 (1986) 493–504. · Zbl 0612.65019 · doi:10.1007/BF01935055 |
[6] | G. Di Lena, D. Trigiante,Stability and spectral properties of incomplete factorization, Jap. Jour. of Appl. Math. 7, 1, 1990, 145–163. · Zbl 0694.65047 · doi:10.1007/BF03167896 |
[7] | A. Graham,Nonnegative matrices and applicable topics in linear algebra, (1987), John Wiley. · Zbl 0625.15011 |
[8] | J. A. Meijerink, H. A. Van der Vorst,Guidelines for the usage of incomplete decompositions in solving sets of linear equations as they occur in practical problems. J. Comput. Phys. 44 (1981) 134–155. · Zbl 0472.65028 · doi:10.1016/0021-9991(81)90041-3 |
[9] | G. Meurant,Multitasking the conjugate gradient method on the CRAY X-MP/48, Parallel Comp. 5 (1987) 267–280. · Zbl 0625.65025 · doi:10.1016/0167-8191(87)90037-8 |
[10] | R. S. Varga,Matrix iterative analysis, (1962) Prentice-Hall, Englewood Cliffs. · Zbl 0133.08602 |
[11] | Microway Parallel Fortran User Guide. |
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.