Recursive Algorithm 5.1. Recursive Symmetric Indefinite Factoriza-
tion (RSIF) of A
1:m,1:n
, m = n:
k = 1
if (n = 1)
Define the pivot: 1×1, or 2×2.
Apply interchanges if necessary
k = k + 1, or k = k + 2
If the pivot is 2×2: FLAG = 1
else
nl = n/2
n2 = n – n1
RSIF of A
:,k:k+n1–1
if (FLAG = 1)
n1 = n1 + 1
n2 = n – n1
end
update A
:,k:k+n2–1
RSIF of A
:,k:k+n1–1
end
185
References
1. B.S. Andersen, F. Gustavson and J. Waśniewski: "A recursive formula-
tion of Cholesky factorization of a matrix in packed storage", Univer-
sity of Tennessee, Knoxville, TN, Computer Science Dept. Technical
Report CS-00-441, May 2000, also LAPACK Working Note number
146 (lawn146.ps), and submitted to the Transaction of Mathematical
Software (TOMS) of the ACM.
2. E. Anderson, Z. Bai. C. H. Bischof. S. Blackford. J. Demmel, J. J.
Dongarra, J.Du Croz, A.Greenbaum, S.Hammairling, A. McKenney,
and D. C. Sorensen. LAPACK Users' Guide Release 3.0. SIAM, Phila-
delphia, 1999.
3. B.S. Andersen. F. Gustavson, J. Waśniewski, and P. Yalamov: Recur-
sive formulation of some dense linear algebra algorithms, in Proceed-
ings of the 9
th
SIAM Conference on Parallel Processing for Scientific
Computing, PPSC99, B. Hendrickson, K.A. Yelick, C.H. Bischof, I.S.
Duff, A.S. Edelman, G.A. Geist, M.T. Heath, M.A. Heroux, C. Koel-
bel, R.S. Schreiber, R.F. Sincovec, and M.F. Wheeler (Eds.), San An-
tonio, TX, USA, March 24–27, 1999, SIAM, Scientific Computing,
CDROM.
4. J.W.
Demmel,
Applied Numerical Linear Algebra. SIAM, Philadelphia,
1997.
5. J. Dongarra and J. Waśniewski, High Performance Linear Algebra
Package - LAPACK90, in Advances in Randomized Parallel Comput-
ing, Kluwer Academic Publishers, Combinatorial Optimization Series,
P.M. Pardalos and S. Rajasekaran (Eds.), 19139 and available as the
LAPACK Working Note (Lawn) Number 134: http://www.not
Iib.org/lapack/lawns/lawn134.ps
6. G.H. Golub and C.F. Van Loan, Matrix Computations (third edition).
Johns Hopkins University Press, Baltimore, MD, 1996.
7. A. Gupta, F. Gustavson, A. Karaivanov, J. Waśniewski, and P. Ya-
lamov, Experience with a Recursive Perturbation Based Algorithm for
Symmetric Indefinite Linear Systems, in: Proc. EuroPar'99, Toulouse,
France, 1999.
8. F. Gustavson, Recursive Leads to Automatic Variable Blocking for
Dense Linear-Algebra Algorithms. IBM Journal of Research and De-
velopment, Volume 41, Number 6, November 1997.
186
9. F. Gustavson, A. Henriksson, I. Jonsson, B. Kågström and P. Ling,
Recursive Blocked Data Formats and BLAS' for Dense Linear Algebra
Algorithms, in Proceedings of the 4
th
International Workshop, Applied
Parallel Computing, Large Scale Scientific and Industrial Problems,
PARA '98, B. Kågström, J. Dongarra, E. Elmroth, and J. Waśniewski
(Eds.), Umeå, Sweden, June 1998, Springer, Lecture Notes in Com-
puter Science Number 1541. pp. 195–206.
10. F. Gustavson, A. Henriksson, I. Jonsson, B. Kågström and P. Ling,
Superscalar GEMM-based Level 3 BLAS - The On-going Evolution of
Portable and High-Performance Library, in Proceedings of the 4
th
In-
ternational Workshop, Applied Parallel Computing, Large Scale Scien-
tific and Industrial Problems, PARA'98, B. Kågström, J. Dongarra, E.
Elmroth, and J. Waśniewski (Eds.), Umeå, Sweden, June 1998,
Springer, Lecture Notes in Computer Science Number 1541, pp. 207–
215.
11. F. Gustavson, A. Karaivanov, M. Marinova, J. Waśniewski, and Pla-
men Yalamov, A Fast Minimal Storage Symmetric Indefinite Solver, in
Lecture Notes in Computer Science, Springer Volume 1947, Editors: T.
Soerevik, F. Manne, R. Moe, A.H. Gebremedhinr,. PARA'2000, Ber-
gen, Norway, June, 2000.
12. F. Gustavson, A. Karaivanov, J. Waśniewski, and P. Yalamov, A
columnwise recursive perturbation based algorithm for symmetric
indefinite linear systems, in: Proc. PDPTA'99, Las Vegas. 1999.
13. N.J. Higham. Accuracy and Stability of Numerical Algorithms. SIAM,
Philadelphia, 1.996.
14. B. Kågström, P. Ling, and C. Van Loan, GEMM-based level 3 BIAS:
High-performance model implementations and performance evaluation
benchmark. ACM Trans. Math. Software, 1997.
15. S. Metcalf and J. Reid. Fortran 90/95 Explained. Oxford, New York,
Tokyo, Oxford University Press, 1996.
16. S. Toledo, Locality of Reference in LU Decomposition with Partial
Pivoting. SIAM Journal on Matrix Analysis and Applications, Vol. 18,
No. 4, 1997.
17. L.N. Trefethen and D. Bau. III. Numerical Linear Algebra. SIAM,
Philadelphia, 1997.
18. J. Waśniewski, B.S. Andersen, and F. Gustavson. Recursive Formula-
tion of Cholesky Algorithm in Fortran 90, in Proceedings of the 4
ift
In-
187
ternational Workshop, Applied Parallel ( Computing, Large Scale Sci-
entific and Industrial Problems. PARA'98. B. Kågström, J. Dongarra,
E. Elmroth, and J. Waśniewski (Eds.), Umeå, Sweden, June 1998,
Springer, Lecture Notes in Computer Science Number 1541, pp. 574–
578.
19. R.C. Whaley and J. Dongarra, Automatically Tuned Linear Algebra
Software (ATLAS), in Ongoing Projects, The Innovative Computing
Laboratory, Distributed Network Computing, Numerical Linear Alge-
bra, Software Repositories, and Performance Evaluation,
http://www.netlib.org/atlas/, Knoxville, Tennessee, USA, 1999.
20. BLAS (Basic Linear Algebra Subprograms), in Ongoing Projects, The
Innovative Computing Laboratory, Distributed Network Computing,
Numerical Linear Algebra, Software Repositories, and Performance
Evaluation, http://www.netlib.org/blas/, Knoxville, Tennessee, USA,
1999.
Достарыңызбен бөлісу: |