![](https://csd.cmu.edu/sites/default/files/styles/full_width_focal_point/public/graduate.png.webp?itok=Wsy3nMEH)
Donald Heller
Thesis Title:
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