A practical parallel algorithm for solving band symmetric positive definite systems of linear equations
Ilan Bar‐On · ACM Transactions on Mathematical Software · 1987
We give a practical parallel algorithm for solving band symmetric positive definite systems of linear equations in O ( m * log n ) time using nm /log n processors. Here n denotes the system size and m its bandwidth. Hence, the algorithm is efficient. For tridiagonal systems, the algorithm runs in O (log n ) time using n /log n processors. Furthermore, an improved version runs in O (log m log n ) time using nm 2 /(log m log n ) processors.