| Автор | Broyden, C.G. |
| Дата выпуска | 1996 |
| dc.description | It is well-known that when methods of conjugate gradient type are applied to non-symmetric or indefinite symmetric systems, breakdown can occur due to division by zero even if exact arithmetic is used. In this paper necessary and sufficient conditions for the absence of breakdown are obtained in terms of the underlying Krylov sequences for both the Lanczos version and the Hestenes-Stiefel version of the block CG algorithm. These conditions are then related to the definiteness or otherwise of the fundamental matrices that define the algorithm and the Lanczos versions are shown to be inherently more stable than the Hestenes-Stiefel ones. Finally the robustness of several well-known special cases of the algorithm is assessed in the light of the results obtained previously |
| Формат | application.pdf |
| Издатель | Gordon and Breach Science Publishers |
| Копирайт | Copyright Taylor and Francis Group, LLC |
| Название | A breakdown of the block CG method |
| Тип | other |
| DOI | 10.1080/10556789608805643 |
| Electronic ISSN | 1029-4937 |
| Print ISSN | 1055-6788 |
| Журнал | Optimization Methods and Software |
| Том | 7 |
| Первая страница | 41 |
| Последняя страница | 55 |
| Аффилиация | Broyden, C.G.; Facolta di Scienze Matematiche, Fisiche Naturali, Corso di Laurea in Scienze del' Informatione, Universita degli Studi di Bologna |
| Выпуск | 1 |
| Библиографическая ссылка | Brezinski, C., Zaglia, M.R. and Sadok, H. 1991. Avoiding breakdown and near-breakdown in Lanczos type algorithms. Numer. Algoriths, 1: 261–284. |
| Библиографическая ссылка | Zaglia, M.R. and Sadok, H. 1992. A breakdown-free Lanczos-type algorithm for solving linear systems. Numer. Math, 63: 29–38. |
| Библиографическая ссылка | Broyden, C.G. 1992. A new taxonomy of conjugate gradient methods. Computers and Mathematics with Applications, 63 To appear |
| Библиографическая ссылка | Broyden, C.G. 1995. A note on the block conjugate gradient algorithm of O'Leary. Optimization Methods and Software, 5: 347–350. |
| Библиографическая ссылка | Broyden, C.G. and Boschetti, M.A. “A comparison of three basic conjugate direction methods”. In Numerical Linear Algebra with Applications, Submitted for publication. |
| Библиографическая ссылка | Fletcher, R. Conjugate gradient methods for indefinite systems. Proceedings of Dundee Conference on Numerical Analysis. Berlin. Edited by: Watson, G.A. Springer Heidelberg:Berlin-Lecture Notes in Mathematics 506 |
| Библиографическая ссылка | Freund, R.W. and Nachtigal, N.M. 1991. Qmr:A quasi-minimal residual method for non-hermitian linear systems. Numer. Math, 60: 315–339. |
| Библиографическая ссылка | Gutknecht, M. 1992. A completed theory of the unsymmetric Lanczos process and related algorithms. SIAM J. Matrix Anal. Appl, 13: 594–639. part 1 |
| Библиографическая ссылка | Gutknecht, M. 1994. A completed theory of the unsymmetric Lanczos process and related algorithms. SIAM J. Matrix Anal. Appl, 15: 15–58. part 2 |
| Библиографическая ссылка | Hegedüs, C. 1990. Generating conjugate directions for arbitrary matrices by matrix equations, Budapest: Central Research Institute for Physics. Technical Report KFKI-1990-36/M, Hungarian Academy of Sciences |
| Библиографическая ссылка | Hestenes, M.R. and Stiefel, E. 1952. Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bureau of Standards, 49: 409–436. |
| Библиографическая ссылка | Horn, R.A. and Johnson, C.A. 1985. Matrix Analysis, Cambridge University Press. |
| Библиографическая ссылка | Lanczos, C. 1950. Solution of systems of linear equations by minimized iterations. J. Res. Nat. Bureau of Standards, 49: 255–282. |
| Библиографическая ссылка | Luenberger, D.G. 1969. Hyperbolic pairs in the method of conjugate gradients. SIAM J. Appl. Math, 17: 1263–1267. |
| Библиографическая ссылка | Nazareth, L. 1977. A conjugate gradient algorithm without line searches. JOTA, 23(3): 373–387. |
| Библиографическая ссылка | Nikishin, A.A. and Yeremin, A.Y. 1995. Variable block cg algorithms for solving large sparse symmetric positive definite linear systems on parallel computers, 1:General iterative scheme. SIAMJ. Matrix. Anal. Appl, 16(4): 1135–1153. |
| Библиографическая ссылка | O'Leary, D.P. 1980. The block conjugate gradient algorithm and related methods. Linear Algebra Applies, 29(4): 293–322. |
| Библиографическая ссылка | Paige, C.C. and Saunders, M.A. 1975. Solution of sparse indefinite systems of linear equations. SIAMJ. Numer. Anal, 12(4): 617–629. |
| Библиографическая ссылка | Paige, C.C. and Saunders, M.A. 1982. An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Software, 6(1): 43–71. |
| Библиографическая ссылка | Parlett, B.N., Taylor, D.R. and Liu, Z.A. 1985. A look-ahead Lanczos algorithm for unsymmetric matrices. Math. Comp, 44(1): 105–124. |
