Email this article Nonlinear growth of the Chebyshev norm of matrices under maximal cross approximation
- Authors: Fedorovskii S.S.1,2
-
Affiliations:
- Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
- Moscow Center of Fundamental and Applied Mathematics, Moscow, Russia
- Issue: Vol 216, No 10 (2025)
- Pages: 159-168
- Section: Articles
- URL: https://journals.rcsi.science/0368-8666/article/view/331249
- DOI: https://doi.org/10.4213/sm10338
- ID: 331249
Cite item
Open Access
Access granted
Subscription Access
Abstract
For the function $g(n)$ describing the maximal possible growth of the Chebyshev norms of maximal cross approximations of an $n\times n$ matrix, the inequality $4g(2k)\leqslant g(7k+3)$ is proved. The bound $g(n)\geqslant Cn^{\log_{7/2}4}$ is established on this basis.
Keywords
About the authors
Semyon Sergeevich Fedorovskii
Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia; Moscow Center of Fundamental and Applied Mathematics, Moscow, Russia
Email: semenfedorovskiy@gmail.com
without scientific degree, no status
References
- J. H. Wilkinson, “Error analysis of direct methods of matrix inversion”, J. ACM, 8:3 (1961), 281–330
- L. Tornheim, Pivot size in Gauss reduction, Tech. paper, Chevron Research Co., Richmond, CA, 1964
- C. W. Cryer, “Pivot size in Gaussian elimination”, Numer. Math., 12:4 (1968), 335–345
- J. Day, B. Peterson, “Growth in Gaussian elimination”, Amer. Math. Monthly, 95:6 (1988), 489–513
- N. Gould, “On growth in Gaussian elimination with complete pivoting”, SIAM J. Matrix Anal. Appl., 12:2 (1991), 354–361
- A. Edelman, “The complete pivoting conjecture for Gaussian elimination is false”, Mathematica J., 2:2 (1992), 58–61
- A. Bisain, A. Edelman, J. Urschel, “A new upper bound for the growth factor in Gaussian elimination with complete pivoting”, Bull. Lond. Math. Soc., 57:5 (2025), 1369–1387
- A. Edelman, J. Urschel, “Some new results on the maximum growth factor in Gaussian elimination”, SIAM J. Matrix Anal. Appl., 45:2 (2024), 967–991
Supplementary files
