On the tripling algorithm for large-scale nonlinear matrix equations with low rank structure

For the large-scale nonlinear matrix equations with low rank structure, the well-developed doubling algorithm in low rank form (DA-LR) is known as an efficient method to compute the stabilizing solution. By further analyzing the global efficiency index constructed in this paper, we propose a tripling algorithm in low rank form (TA-LR) from two points of view, the cyclic reduction and the symplectic structure preservation. The new presented algorithm shares the same pre-processing complexity with that of DA-LR, but can attain the prescribed normalized residual level within less iterations by only consuming some negligible iteration time as an offset. Under the solvability condition, the proposed algorithm is demonstrated to inherit a cubic convergence and is capable of delivering errors from the current iteration to the next with the same order. Numerical experiments including some from nano research show that the TA-LR is highly efficient to compute the stabilizing solution of large-scale nonlinear matrix equations with low rank structure.