Row-Oriented Direct Solving of Linear Algebraic Equations; Row Orthogonalization Method

摘要

Serial and parallel algorithms are discussed, derived from a direct row-oriented solution method for linear algebraic equations: the 'row orthogonalization' method. Like in another row-oriented method, the 'inverse projection' method, no elimination of unknowns is applied. The matrix equation is considered to be a set of inner product equations. For the 'row orthogonalization' method the set of inner product equations is transformed into one with orthogonal row vectors by applying orthogonalization techniques to the original row vectors. The resulting equations can independently be solved. The transforming and solving process requires extensive inner product calculus. Pipelined as well as parallel processing can be applied, resulting in parallel algorithms with a large speed-up, which can easily and efficiently be implemented onto MIMD supercomputers provided with local memories and designed to perform both parallel and pipelined processing. In case of structured sparse matrices the structural characteristics can be exploited resulting in a considerable speed improvement. (Copyright (c) 1988 by Faculty of Technical Mathematics and Informatics, Delft, The Netherlands.)