The QIF parallel method for linear systems, eigenvalue and singular value computations
Briones, Dante Medrano
MetadataShow full item record
A new factorization, the Quadrant Interlocking Factorization (QIF), is used to solve the linear system Ax = b in O(n²) steps using O(n²) processors. The matrix A is factored into a product of its quadrant interlocking factors W and Z, i.e., A = WZ, instead of the usual LU factorization. Variations of the WZ factorization are derived, namely, WDZ, WDW^(t) and WWt which are analogous to the variations of the LU factorization, namely, LDU, LDL^(t) and LL^(t), respectively. The inertia of a nonsingular symmetric matrix A is found using the WDW^(t) factorization. The QZ factorization of a symmetric positive definite matrix A is presented. This factorization is analogous to the QR factorization of A. The QZ factorization is used implicitly to compute the eigenvalues of a symmetric positive definite matrix in 0(nlog₂n) steps per iteration using 0(n²) processors. A new algorithm is used to solve for the singular values of a square matrix using the WZ and WW^(t) factorizations in 0(nlog₂n) steps per iteration using O(n²) processors. The algorithms discussed in this thesis are well suited for Single Instruction Multiple Data (SIMD) machines.