Parallel implementations of Modified Gram-Schmidt orthogonalization /
Interest in the QR factorization arises from the ographics.
| Main Author: | |
|---|---|
| Format: | Thesis Book |
| Language: | English |
| Published: |
[Place of publication not identified] :
[publisher not identified] ;
1998.
|
| Subjects: |
| Summary: | Interest in the QR factorization arises from the ographics. important role it plays in a large number of computational algorithms in linear algebra such as the estimation of least squares and the calculation of eigenvalues and eigenvectors. The basic idea consists of calculating the factorization of an 'rn x n matrix W, where m k zs. That is, finding Q and R where ,4 = QR, Q is an orthonormal matrix (QTQ = f ), and R is upper triangular. Gram-Schmidt orthogonalization is a classical mathematical procedure for solving the orthogonal bases problem. A particular important modification of the numerically unstable classical Gram-Schmidt is known as the Modified Gram-Schmidt (MGS) algorithm. The importance of the QR factorization in numerical matrix calculation and its high algorithmic complexity, which is around O(mn2 ) , has motivated a huge interest in obtaining efficient parallel implementation. Here, implementation of parallel Gram-schmidt orthogonalization algorithms are analyzed. Four types of column-wise partitioning schemes including one-column, block, cyclic and block- cyclic partitioning, and a row-wise partitioning of O'Leary and Whitman were considered. Analytical models for parallel execution time required by these implementations are derived and compared with numerical results. Threshold values of ['rrlraaz], which is the number of rows where row partitioning becomes better than column partitioning are found theoretically and verified numerically. Our theoretical analysis of column-wise algorithms, which were implemented using pipelined fashion predicts architecture independence. An important application of the orthogonal factorization, the least squares problem is discussed and other applications are presented. |
|---|---|
| Item Description: | "Major subject: Computer Science". Vita. |
| Physical Description: | vii, 73 leaves : illustrations ; 28 cm. |
| Bibliography: | Includes bibliographical references: pages 61-72. |