Cyclic Reduction

Bandwidth (or semibandwidth) of n × n matrix A is smallest value β such that aij = 0 for all |i − j |> β Matrix is banded if β n If β p, then minor modifications of parallel algorithms for dense LU or Cholesky factorization are reasonably efficient for solving banded linear system Ax = b If β / p, then standard parallel algorithms for LU or Cholesky factorization utilize few processors and are very inefficien