Partial Fraction Decomposition of Matrices and Parallel Computing

Abstract

We are interested in the design of parallel numerical schemes for linear systems. We give an effective solution to this problem in the following case: the matrix $A$ of the linear system is the product of $p$ nonsingular matrices $A_i^m$ with specific shape: $A_i= I -{h_i}X$ for a fixed matrix $X$ and real numbers $h_i$. Although having a special form, these matrices $A_i$ arise frequently in the discretization of evolutionary Partial Differential Equations. For example, one step of the implicit Euler scheme for the evolution equation $u' =Xu$ reads $(I-hX)u^{n+1}=u^n$. Iterating $m$ times such a scheme leads to a linear system $Au^{n+m}=u^n$. The idea is to express $A^{-1}$ as a linear combination of elementary  matrices $A_i^{-1}$ (or more generally in term of matrices $A_i^{-k}$). Hence the solution of the linear system with matrix $A$ is a linear combination of the solutions of linear systems with matrices $A_i$ (or $A_i^k$). These systems are then solved simultaneously on different processors.