Donald Heller

The Solution of Block Tri-diagonal Linear Systems on Parallel Computers Degree Type: Ph.D. in Computer Science
Advisor(s): Joseph Traub
Graduated: August 1977

Abstract:

Block tridiagonal systems of linear equations occur frequently in scientific computations , often forming the core of more complicated problems. Numerical methods for solution of such systems are studied with emphasis on efficient methods for a vector computer. A convergence theory for direct methods under conditions of block diagonal dominance is developed, demonstrating stability, convergence and approximation properties of direct methods. Block elimination (LU factorization) is linear, cyclic odd-even reduction is quadratic, and higher-order methods exist. The odd-even methods are variations of the quadratic Newton iteration for the inverse matrix, and are the only quadratic methods within a certain reasonable class of algorithms. Semi-direct methods based on the quadratic convergence of odd-even reduction prove useful in combination with linear iterations for an approximate solution. An execution time analysis for a pipeline computer is given, with attention to storage requirements and the effect of machine constraints on vector operations.

Thesis Committee:
Joseph Traub (Chair)

Joseph Traub, Head, Computer Science Department