A structure-preserving doubling algorithm for the quadratic matrix equation with $M$-matrix

We consider the solution of the large-scale quadratic matrix equation $X^2 + BX + C = 0$, with $B$ and $C$ being large-scale and low-ranked. In the quadratic matrix equation arisen from an overdamped vibrating system, $B$ is a nonsingular $M$-matrix and $C$ is an $M$-matrix such that $B^{-1} C \geq 0$ and $B-C-I$ is a nonsingular $M$-matrix. The structure-preserving doubling algorithm by Guo, Lin and Xu (2006) is adapted, with the appropriate applications of the Sherman–Morrison–Woodbury formula and the sparse-pluslow- rank representations of various iterates. The resulting largescale doubling algorithm has an $O(n)$ computational complexity and memory requirement per iteration and converges essentially quadratically, as illustrated by the numerical examples.

Keywords

structure-preserving doubling algorithm, $M$-matrix, quadratic matrix equation, numerically low-ranked solution, overdamped vibrating system

Full Text (PDF format)

This work was supported by (a) Career Development Award of Academia Sinica (Taiwan) grant number 103-CDA-M04 and (b) Ministry of Science and Technology (Taiwan) grant number 103-2811-M-001-166.

Received 13 April 2023

Accepted 2 May 2023

Published 15 August 2024