Component-wise accurate computation of the square root of an M-matrix

Abstract

Component-wise accurate algorithms for computing the principal square root of an M-matrix are designed in terms of triplet representations. A triplet representation of an M-matrix $A$ is the triple $(P,\mathbf{u},\mathbf{v})$, where the matrix $P$ is such that $p_{ij}=-a_{ij}$ for $i\ne j$, $p_{ii}=0$, and $\mathbf{u}>0$, $\mathbf{v}\ge 0$ are two vectors such that $A\mathbf{u}=\mathbf{v}$. It is shown that if $A$ is an M-matrix representable by a triplet, then its principal square root exists and is an M-matrix represented by a triplet as well. New versions of the Cyclic Reduction and the Incremental Newton iterations are provided in terms of triplets, to compute the principal matrix square root of $A$. It is shown that these algorithms are component-wise numerically stable independently of the singularity of $A$ and of its condition number. Numerical experiments are shown to confirm the component-wise stability.