Solving large-scale nonlinear matrix equations by doubling

Peter Chang Yi Weng, Eric King Wah Chu*, Yueh Cheng Kuo, Wen-Wei Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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.

Original languageEnglish
Pages (from-to)914-932
Number of pages19
JournalLinear Algebra and Its Applications
Issue number4
StatePublished - 1 Jan 2013


  • Doubling algorithm
  • Green's function
  • Krylov subspace
  • Leaky surface wave
  • Nano research
  • Nonlinear matrix equation
  • Surface acoustic wave

Fingerprint Dive into the research topics of 'Solving large-scale nonlinear matrix equations by doubling'. Together they form a unique fingerprint.

Cite this