Solving large-scale nonsymmetric algebraic Riccati equations from two-dimensional transport models by doubling

摘要

We consider the solution of the large-scale nonsymmetric algebraic Riccati equation XCX - XD - AX + B = 0, with M equivalent to [D, -C; -B, A] is an element of R(n1+n2)x(n1+n2) being a nonsingular M-matrix, and A, D being sparse-like, with the products A(-1)u, A(-T)u, D(-1)v and D(-T)v computable in O(n(1)) or O(n(2)) complexity, for some vectors u and v. In the nonsymmetric algebraic Riccati equation arose from a two-dimensional transport model, B, C are low-ranked corrections of some invertible diagonal matrices. 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 plus-low-rank representations of various iterates. The resulting large-scale doubling algorithm has an O(n) computational complexity and memory requirement per iteration (with n = max{n(1), n(2)}) and converges essentially quadratically, as illustrated by the numerical examples. (c) 2021 Elsevier B.V. All rights reserved.