Stability of block. (English) Zbl 0834.65010

Demmel, James W.; Higham, Nicholas J.; Schreiber, Robert S.

Numer. Linear Algebra Appl. 2, No. 2, 173-190 (1995).

The architecture of modern vector and parallel computers has lead to an increased interest in block algorithms such as block Gaussian elimination. A straightforward generalization of the scalar algorithm has previously been shown to be unstable in general. In this paper some positive results are established. Among them is a proof that if the matrix is block diagonal dominant by column, then the algorithm is stable provided the matrix is well-conditioned. A similar result is given for the positive definite symmetric case.
The authors note that LAPACK includes partitioned algorithms rather than block algorithms of this type. For the partitioned algorithms the operations of the scalar algorithms are reordered. The classical stability analysis can then be employed.

Reviewer: O.Widlund (New York)

MSC:

65F05	Direct numerical methods for linear systems and matrix inversion
65Y05	Parallel numerical computation

Keywords:

block LU factorization; parallel computation; well-conditioned matrix; block algorithms; block Gaussian elimination; stability

Software:

LAPACK

References:

[1]	Dongarra, J. Comp. Appl. Math. 27 pp 215– (1989)
[2]	Gallivan, Int. J. of Supercomputer Applics. 2 pp 12– (1988)
[3]	Gallivan, SIAM Review 32 pp 54– (1990)
[4]	, , , , , , , , and , LAPACK Users’ Guide. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992.
[5]	Dongarra, ACM Trans. Math. Soft. 16 pp 1– (1990)
[6]	Dongarra, ACM Trans. Math. Soft. 16 pp 18– (1990)
[7]	, and . Solving Linear Systems on Vector and Shared Memory Computers, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1991.
[8]	and . Matrix Computations. Johns Hopkins University Press, Baltimore, MD, Second edition, 1989.
[9]	Demmel, ACM Trans. Math. Soft. 18 pp 274– (1992)
[10]	Du Croz, IMA Journal of Numerical Analysis 12 pp 1– (1992)
[11]	Bischof, SIAM J. Sci. Stat. Comput. 8 pp s2– (1987)
[12]	Block algorithms for parallel machines. In Numerical Algorithms for Modern Parallel Computer Architectures, editor. Number 13 in IMA Volumes in Mathematics and its Applications, pp. 197-207. Springer-Verlag, Berlin, 1988. · doi:10.1007/978-1-4684-6357-6_12
[13]	Bai, Int. J. High Speed Computing 1 pp 97– (1989)
[14]	Block methods for solving sparse linear systems. In Sparse Matrix Computations, and , editors, pp. 39-58. Academic Press, New York, 1976. · doi:10.1016/B978-0-12-141050-6.50008-8
[15]	Mattheij, SIAM J. Alg. Disc. Meth. 5 pp 314– (1984)
[16]	Eugene Isaacson and Herbert Bishop Keller, Analysis of Numerical Methods, John Wiley, New York, 1966.
[17]	Mattheij, Bull. Austral. Math. Soc. 29 pp 177– (1984)
[18]	Varah, Math. Comp. 26 pp 859– (1972)
[19]	Bank, SIAM J. Numer. Anal. 14 pp 792– (1977)
[20]	Wilkinson, J. Assoc. Comput. Mach. 8 pp 281– (1961) · Zbl 0109.09005 · doi:10.1145/321075.321076
[21]	and . Componentwise error analysis for stationary iterative methods. In Linear Algebra, Markov Chains, and Queueing Models, and , editors. Volume 48 of IMA Volumes in Mathematics and its Applications, pp. 29-46. Springer-Verlag, New York, 1993. · Zbl 0794.65034 · doi:10.1007/978-1-4613-8351-2_3
[22]	Woźniakowski, Numer. Math. 30 pp 301– (1978)
[23]	Feingold, Pacific J. Math. 12 pp 1241– (1962) · Zbl 0109.24802 · doi:10.2140/pjm.1962.12.1241
[24]	Polman, Linear Algebra and Appl. 90 pp 119– (1987)
[25]	Trefethen, SIAM J. Matrix Anal. Appl. 11 pp 335– (1990)
[26]	Varah, Linear Algebra and Appl. 11 pp 3– (1975)
[27]	Demmel, SIAM J. Numer. Anal. 20 pp 599– (1983)
[28]	Higham, ACM Trans. Math. Soft. 17 pp 289– (1991)
[29]	How accurate is Gaussian elimination?. In Numerical Analysis 1989, Proceedings of the 13th Dundee Conference, and , editors. Volume 228 of Pitman Research Notes in Mathematics, pp. 137-154. Longman Scientific and Technical, Essex, UK, 1990.
[30]	Higham, BIT 31 pp 447– (1991)