Parallel algorithms for band SPD systems of linear equations

Candidate: Bar-On,Ilan


In this thesis we consider parallel algorithms for solving band symmetric positive definite systems of linear equations where the number of equations is much larger than the band width. Such systems arise in many practical applications for the dynamic analysis of structures such as the design of dams, bridges, ships, supersonic jets etc. Sequential methods for solving these systems require intolerable turnaround times and hence the importance of fast parallel algorithms for solving them. Our main contribution in this thesis is the presentation of a new practical parallel algorithm. Our algorithm runs in O(m $\*$ log n) time using nm/log n processors where n is the number of equations and m the band width. Hence, the algorithm is efficient. For tridiagonal systems the algorithm runs in O(log n) time using n/log n processors. We also develop a theoretical faster algorithm that runs in O(log m log n) time using nm$\sp2$/(log m log n) processors. This algorithm is efficient and runs as fast as the best currently known theoretical method. In chapter one we introduce the basic principles of parallel computations. In chapter two we review the basic algebraic and numerical properties of matrix computations. Here, we present a new parallel efficient algorithm for adding n k-bits integers in O(log n + log k) time based on the Fibbonachi sequence. In chapter three we consider parallel methods for solving band triangular systems which arise from the L-U decomposition of A. We conclude that this method is not as efficient for parallel computers as for sequential ones. In chapter four, we give a new efficient parallel algorithm for inverting a s.p.d. matrix in O(log$\sp2$n) time. We then present our new parallel algorithm for solving band s.p.d. systems, analyse its complexity, and show its improvement over the odd-even reduction algorithm. We conclude by pointing to yet unresolved problems in this field.