Variations on the Gram-Schmidt and the Huang algorithms for linear systems: A numerical study

Spedicato, Emilio ; Vespucci, Maria Teresa

Applications of Mathematics, Tome 38 (1993) no. 2, pp. 81-100

Abstract (VO)

In this paper we compare the numerical performance on a set of ill conditioned problems of several algorithms for linear systems based upon the explicit QR factorization and the implicit LQ factorization associated with the Huang and the modified Huang algorithms in the ABS class. The results indicate that the modified Huang algorithm is generally more accurate than the Huang algorithm and competitive with commercial codes based upon the QR factorization with Householder of Givens reflections. The best version of the modified Huang algorithm performs similarly, as theoretically expected, to the doubly iterated Gram-Schmidt method of Daniel et al., applied on the rows to generate search vectors.

Détail

DOI : 10.21136/AM.1993.104537

Classification : 65F05, 65F10
Keywords: ABS methods; Huang algorithm; QR algorithm; Gram-Schmidt orthogonalization; ill-conditioned equations; numerical experiments

Bibliographie

[1] Abaffy J.: Equivalence of a generalization of Sloboda's algorithm with a subclass of the generalized ABS algorithm for linear systems. Quaderno DMSIA I/88(1988), University of Bergamo.

[2] Abaffy J., Broyden C. G., Spedicato E.: A class of direct methods for linear equations. Numerische Mathematik 45 (1984), 361-376. | DOI | MR

[3] Abaffy J., Galántai A.: Conjugate direction methods for linear and nonlinear systems of algebraic equations. Colloquia Mathematica Societatis János Bolyai 50 (1986), 481-502. | MR

[4] Abaffy J., Galántai A., Spedicato E.: The local convergence of ABS methods for nonlinear algebraic systems. Numerische Mathematik 51 (1987a), 429-439. | DOI | MR

[5] Abaffy J., Galántai A., Spedicato E.: Application of ABS class to unconstrained function minimization. Quaderno DMSIA 14/77 (1987b), University of Bergamo.

[6] Abaffy J., Spedicato E.: A generalization of the ABS algorithm for linear systems. Quaderno DMSlA 4/85 (1985), University of Bergamo.

[7] Abaffy J., Spedicato E.: Numerical experiments with the symmetric algorithm in the ABS class for linear systems. Optimization 18(2) (1987), 197-212. | DOI | MR | Zbl

[8] Abaffy J., Spedicato E.: ABS projection algorithms: mathematical techniques for linear and nonlinear equations. Ellis Horwood, Chichester, 1989. | MR | Zbl

[9] Broyden C. G.: On the numerical stability of Huang's update. Quaderno DMSIA 18/89 (1989), University of Bergamo. | Zbl

[10] Daniel J., Gragg W. B., Kaufman L., Stewart G. W.: Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization. Mathematics of Computation 30 (1976), 772-795. | MR | Zbl

[11] Deng N. Y., Spedicato E.: Optimal conditioning parameter selection in the ABS class through a rank two update formulation. Quaderno DMSIA 18/88 (1988), University of Bergamo.

[12] Hoffmann W.: Iterative algorithms for Gram-Schmidt orthogonalization. Computing 41 (1989), 335-348. | DOI | MR | Zbl

[13] Huang H. Y.: A direct method for the general solution of a system of linear equations. Journal of Optimization Theory and Applications 16 (1975), 429-445. | DOI | MR | Zbl

[14] More J. J., Cosnard M. Y.: Numerical solution of nonlinear equations. ACM Trans. 5 (1979), 64-85. | MR | Zbl

[15] Rutishauser H.: On test matrices. Progrès en Mathématiques Numériques (M. Kuntzmann, eds.), Editions de la Faculté de Science de Besançon, 1968. | MR | Zbl

[16] Sloboda F.: A parallel projection method for linear algebraic systems. Apl. Mat. Českosl. Akad. Ved 25 (1978), 185-198. | MR | Zbl

[17] Spedicato E.: Optimal conditioning parameter selection in the ABS class for linear systems. Report 203, Mathematische Institute, University of Würzburg, 1987.

[18] Spedicato E., Vespucci M. T.: Variations on the Gram-Schmidt and the Huang algorithms for linear systems: a numerical study. Quaderno DMSIA 21/89(1989), University of Bergamo.

[19] Yang Z.: On the numerical stability of the Huang and the modified Huang algorithms and related topics. Collection of reports on the ABS class of algorithms, 5, Department of Applied Mathematics, Dalian University of Technology, 1988.

[20] Zielke G.: Report on test matrices for generalized inverses. Computing 36 (1986), 105-162. | DOI | MR | Zbl