Incomplete partial fractions for parallel evaluation of rational matrix functions (Q1899990)

This paper is concerned with the evaluation of \(x:= [p(A)]^{- 1} q(A)b\), when \(p\) and \(q\) are polynomials of the matrix \(A\). Such expressions occur when solving Poisson's equation by block cyclic reduction. If \(p\) is factored in a product of linear factors a sequential algorithm results. A parallel algorithm is obtained by computing the partial fraction representation of \([p(A)]^{- 1}\). However, this algorithm may be unstable. The authors propose a compromise by computing an incomplete partial fraction representation with a small number of factors. Algorithms for computing such representations are presented and analyzed.