
Accession Number : AD0765178
Title : Tridiagonalization by Permutations.
Descriptive Note : Technical rept.,
Corporate Author : COLLEGE OF WILLIAM AND MARY WILLIAMSBURG VA DEPT OF MATHEMATICS
Personal Author(s) : Gibbs,Norman E. ; Poole,William G. , Jr
Report Date : AUG 1973
Pagination or Media Count : 20
Abstract : Tridiagonalizing a matrix by similarity transformations is an important computational tool in numerical linear algebra. Consider the class of sparse matrices which can be tridiagonalized using only row and corresponding column permutations. The advantages of using such a transformation include the absence of roundoff errors and improved computation time when compared with standard transformations. A graphtheoretic algorithm which examines an arbitrary nxn matrix and determines whether or not it can be permuted into tridiagonal form is given. The algorithm requires no arithmetic while the number of comparisons, the number of assignments, and the number of increments are linear in n. This compares very favorably with standard transformation methods. If the matrix is permutable into tridiagonal form, the algorithm gives the explicit tridiagonal form. Otherwise, early rejection will occur. (Author)
Descriptors : (*MATRICES(MATHEMATICS), PERMUTATIONS), TRANSFORMATIONS(MATHEMATICS), GRAPHICS, ALGORITHMS
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE