EUVIMEDEUVIMED entdecken
Crossref

On a Randomized Small-Block Lanczos Method for Large-Scale Null Space Computations

Daniel Kressner, Nian Shao

SIAM Journal on Scientific Computing · 31.10.2026 · 48 (5) · S462-S485

DOI: 10.1137/24m1674881 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Scientific Computing, online erschienen am 02.04.2026. Verfasst von Daniel Kressner und 1 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Computing the null space of a large sparse matrix [Formula: see text] is a challenging computational problem, especially if the nullity—the dimension of the null space—is not small. When applying a block Lanczos method to [Formula: see text] for this purpose, conventional wisdom suggests to use a block size [Formula: see text] that is not smaller than the nullity. In this work, we show how randomness can be utilized to allow for smaller [Formula: see text] without sacrificing convergence or reliability. Even [Formula: see text], corresponding to the standard single-vector Lanczos method, becomes a safe choice. This is achieved by using a small random diagonal perturbation, which moves the zero eigenvalues of [Formula: see text] away from each other, and a random initial guess. We analyze the effect of the perturbation on the attainable quality of the null space and derive convergence results that establish robust convergence for [Formula: see text]. As demonstrated by our numerical experiments, a smaller block size combined with restarting and partial reorthogonalization results in reduced memory requirements and computational effort. It also allows for the incremental computation of the null space without requiring a priori knowledge of the nullity. Our algorithm is best suited for situations when the nullity of [Formula: see text] is moderate. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/nShao678/Nullspace-code and in the supplementary materials ( Nullspace-code-main.zip [10.7MB]). [Formula: see text]

Zitieren

APA

Kressner, D., & Shao, N. (2026). On a Randomized Small-Block Lanczos Method for Large-Scale Null Space Computations. SIAM Journal on Scientific Computing, 48(5), S462-S485. https://doi.org/10.1137/24m1674881

Vancouver

Kressner D, Shao N. On a Randomized Small-Block Lanczos Method for Large-Scale Null Space Computations. SIAM Journal on Scientific Computing. 2026;48(5):S462-S485. doi:10.1137/24m1674881

BibTeX
@article{Kressner2026,
  author = {Kressner, Daniel and Shao, Nian},
  title = {On a Randomized Small-Block Lanczos Method for Large-Scale Null Space Computations},
  journal = {SIAM Journal on Scientific Computing},
  year = {2026},
  volume = {48},
  number = {5},
  pages = {S462--S485},
  doi = {10.1137/24m1674881}
}
Kostenlos starten →