TY - JOUR

T1 - Solving large-scale nonlinear matrix equations by doubling

AU - Weng, Peter Chang Yi

AU - Chu, Eric King Wah

AU - Kuo, Yueh Cheng

AU - Lin, Wen-Wei

PY - 2013/1/1

Y1 - 2013/1/1

N2 - We consider the solution of the large-scale nonlinear matrix equation X+BX-1A-Q=0, with A,B,Q,X∈Cn×n, and in some applications B=A (=⊤ or H). The matrix Q is assumed to be nonsingular and sparse with its structure allowing the solution of the corresponding linear system Qv=r in O(n) computational complexity. Furthermore, B and A are respectively of ranks ra,rb≪n. The type 2 structure-preserving doubling algorithm by Lin and Xu (2006) [24] is adapted, with the appropriate applications of the Sherman-Morrison-Woodbury formula and the low-rank updates of various iterates. Two resulting large-scale doubling algorithms have an O((ra+rb)3) computational complexity per iteration, after some pre-processing of data in O(n) computational complexity and memory requirement, and converge quadratically. These are illustrated by the numerical examples.

AB - We consider the solution of the large-scale nonlinear matrix equation X+BX-1A-Q=0, with A,B,Q,X∈Cn×n, and in some applications B=A (=⊤ or H). The matrix Q is assumed to be nonsingular and sparse with its structure allowing the solution of the corresponding linear system Qv=r in O(n) computational complexity. Furthermore, B and A are respectively of ranks ra,rb≪n. The type 2 structure-preserving doubling algorithm by Lin and Xu (2006) [24] is adapted, with the appropriate applications of the Sherman-Morrison-Woodbury formula and the low-rank updates of various iterates. Two resulting large-scale doubling algorithms have an O((ra+rb)3) computational complexity per iteration, after some pre-processing of data in O(n) computational complexity and memory requirement, and converge quadratically. These are illustrated by the numerical examples.

KW - Doubling algorithm

KW - Green's function

KW - Krylov subspace

KW - Leaky surface wave

KW - Nano research

KW - Nonlinear matrix equation

KW - Surface acoustic wave

UR - http://www.scopus.com/inward/record.url?scp=84879878933&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2012.08.008

DO - 10.1016/j.laa.2012.08.008

M3 - Article

AN - SCOPUS:84879878933

VL - 439

SP - 914

EP - 932

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

IS - 4

ER -