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

Emilio Spedicato; Maria Teresa Vespucci

Applications of Mathematics (1993)

  • Volume: 38, Issue: 2, page 81-100
  • ISSN: 0862-7940

Abstract

top
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.

How to cite

top

Spedicato, Emilio, and Vespucci, Maria Teresa. "Variations on the Gram-Schmidt and the Huang algorithms for linear systems: A numerical study." Applications of Mathematics 38.2 (1993): 81-100. <http://eudml.org/doc/15738>.

@article{Spedicato1993,
abstract = {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.},
author = {Spedicato, Emilio, Vespucci, Maria Teresa},
journal = {Applications of Mathematics},
keywords = {ABS methods; Huang algorithm; QR algorithm; Gram-Schmidt orthogonalization; ill-conditioned equations; numerical experiments; ill-conditioned equations; method; method; Huang methods; numerical experiments; algorithms; Huang algorithms; Gram-Schmidt algorithm; update formula},
language = {eng},
number = {2},
pages = {81-100},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Variations on the Gram-Schmidt and the Huang algorithms for linear systems: A numerical study},
url = {http://eudml.org/doc/15738},
volume = {38},
year = {1993},
}

TY - JOUR
AU - Spedicato, Emilio
AU - Vespucci, Maria Teresa
TI - Variations on the Gram-Schmidt and the Huang algorithms for linear systems: A numerical study
JO - Applications of Mathematics
PY - 1993
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 38
IS - 2
SP - 81
EP - 100
AB - 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.
LA - eng
KW - ABS methods; Huang algorithm; QR algorithm; Gram-Schmidt orthogonalization; ill-conditioned equations; numerical experiments; ill-conditioned equations; method; method; Huang methods; numerical experiments; algorithms; Huang algorithms; Gram-Schmidt algorithm; update formula
UR - http://eudml.org/doc/15738
ER -

References

top
  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. (1988) 
  2. Abaffy J., Broyden C. G., Spedicato E., 10.1007/BF01391414, Numerische Mathematik 45 (1984), 361-376. (1984) MR0769246DOI10.1007/BF01391414
  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. (1986) MR0935191
  4. Abaffy J., Galántai A., Spedicato E., 10.1007/BF01397545, Numerische Mathematik 51 (1987a), 429-439. (1987) MR0902099DOI10.1007/BF01397545
  5. Abaffy J., Galántai A., Spedicato E., Application of ABS class to unconstrained function minimization, Quaderno DMSIA 14/77 (1987b), University of Bergamo. (1987) 
  6. Abaffy J., Spedicato E., A generalization of the ABS algorithm for linear systems, Quaderno DMSlA 4/85 (1985), University of Bergamo. (1985) 
  7. Abaffy J., Spedicato E., 10.1080/02331938708843232, Optimization 18(2) (1987), 197-212. (1987) Zbl0616.65032MR0871792DOI10.1080/02331938708843232
  8. Abaffy J., Spedicato E., ABS projection algorithms: mathematical techniques for linear and nonlinear equations, Ellis Horwood, Chichester, 1989. (1989) Zbl0691.65022MR1015928
  9. Broyden C. G., On the numerical stability of Huang's update, Quaderno DMSIA 18/89 (1989), University of Bergamo. (1989) Zbl0711.65021
  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. (1976) Zbl0345.65021MR0431641
  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. (1988) 
  12. Hoffmann W., 10.1007/BF02241222, Computing 41 (1989), 335-348. (1989) Zbl0667.65037MR0993829DOI10.1007/BF02241222
  13. Huang H. Y., 10.1007/BF00933852, Journal of Optimization Theory and Applications 16 (1975), 429-445. (1975) Zbl0291.90038MR0400678DOI10.1007/BF00933852
  14. More J. J., Cosnard M. Y., Numerical solution of nonlinear equations, ACM Trans. 5 (1979), 64-85. (1979) Zbl0393.65019MR0520748
  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. (1968) Zbl0209.17502MR0232536
  16. Sloboda F., A parallel projection method for linear algebraic systems, Apl. Mat. Českosl. Akad. Ved 25 (1978), 185-198. (1978) Zbl0398.65013MR0490260
  17. Spedicato E., Optimal conditioning parameter selection in the ABS class for linear systems, Report 203, Mathematische Institute, University of Würzburg, 1987. (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. (1989) 
  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. (1988) 
  20. Zielke G., 10.1007/BF02238196, Computing 36 (1986), 105-162. (1986) Zbl0566.65026MR0832934DOI10.1007/BF02238196

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.