Paperlane

no. 12 · Tuesday 10 November 2026

A Low-Rank BUG Method for Sylvester-Type Equations

Georgios Vretinaris

math.NA · v2 · 14 pp

Abstract

We introduce a low-rank algorithm inspired by the Basis-Update and Galerkin (BUG) integrator to efficiently approximate solutions to Sylvester-type equations. The algorithm can exploit both the low-rank structure of the solution as well as any sparsity present to reduce computational complexity. In the worst case scenario, i.e. even when a standard dense solver, such as the Bartels-Stewart algorithm, is used for the reduced Sylvester equations generated by our approach, the overall computational complexity for constructing and solving the associated linear systems reduces to $\mathcal{O}\left(kr(n^2+m^2 +mn + r^2)\right)$, for $X\in \mathbb{R}^{m \times n}$, where $k$ is the number of iterations and $r$ the rank of the approximation, but any method can be used to exploit existing structure to optimize the solution even further.

comments
14 pages, 5 figures
fields
Numerical Analysis
pdf ↗ page arXiv:2511.01735 ↗