A Parallel Block Cholesky Factorization for Staircase Linear Programming Problems

We present a variant of the Cholesky factorization for block tridiagonal positive definite matrices. We show that a suitable ordering of block pivots makes it possible to parallelize the linear algebra on a multiple instruction multiple data (MIMD) processor achitecture. The technique applies to linear programming problems with a staircase constraint matrix, a structure that is typical of dynamic (multiperiod, multistage) problems. We compute the amount of parallelism that is theoretically achievable and we show that the increase in block fill-in of the Cholesky factor is limited.