We develop Toeplitz infinite GMRES for solving large sparse analytic parameterized systems $A(s)x(s)=z$ at many parameter values. The method exploits a block upper triangular Toeplitz structure in the companion Krylov sequence to construct the Arnoldi process and recover solution approximations without storing full Arnoldi vectors. We derive incremental recurrences requiring $\mathcal{O}(np^2+p^3)$ arithmetic and $\mathcal{O}(np+p^2)$ storage for $p$ Arnoldi steps, excluding factorization setup and assuming linear-cost coefficient actions and triangular solves. A dynamic generator-refreshing strategy addresses cancellation in the basic recurrence. For matrix functions admitting a fixed separated representation, we further develop an implicitly rebased method based on a compact, contractive nilpotent matrix. Both variants preserve the Arnoldi process in exact arithmetic, with exact matrix-function actions required for the rebased method. A residual lower bound for square-summable Taylor coefficients explains a scaling obstruction outside the normalized unit disk. Theoretical analysis and numerical experiments illustrate the computational efficiency of the proposed methods.
Extended Krylov subspace methods (EKSMs) are a well known approach for approximating the action of a matrix function on a vector $f(A)\mathbf{b}$, and their block versions are often used for solving Lyapunov and Sylvester matrix equations. EKSMs produce Laurent approximations to the underlying operator, which are gener...
Short-recurrence Krylov methods that are equivalent in exact arithmetic often diverge in floating-point arithmetic. To illustrate this, we provide an exactly representable two-cycle for steepest descent with a recursively updated residual. A complementary convergence theorem gives a sufficient condition under which the...
We present a new asymptotic matrix multiplication construction yielding $\omega<2.37115924$, and therefore an algorithm that multiplies two $n\times n$ matrices in $O(n^{2.37115924})$ arithmetic operations over the rationals, reals, or complex numbers. The construction improves the bound $2.371177$ of Dupont et al. wit...
The low-rank alternating direction implicit (ADI) method is an efficient solver for large-scale Stein equations with low-rank solutions. This paper shows that, as in the continuous-time Lyapunov equation case, the low-rank Cholesky factor ADI (LRCF-ADI) method for Stein equations implicitly performs $\mathcal{H}_2$-pse...
Let $A$ and $B$ be polynomials with integer coefficients. We study nonzero integer solutions of $$y\mid A(x),\qquad x\mid B(y),$$ using quotient transformations that may change the polynomial pair. We call this process \emph{congruence jumping}. We establish a general reciprocal-polynomial rule governing such jumps, wi...
We study when a polynomial sequence $\{p_n(x)\}$ satisfying a linear homogeneous recurrence with polynomial coefficients admits an ordinary Riordan array as its coefficient matrix. For second-order recurrences $p_{n+2}(x)=a(x)p_{n+1}(x)+b(x)p_n(x)$, we give a complete characterization. We extend this to a necessary con...
Tian-Xiao He· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
