Optimal sign approximation with a multiplication budget
For an integer $m \ge 0$ let $\mathcal P_m$ be the set of real polynomials obtained from $1$ and $x$ by arbitrarily many real linear combinations of polynomials already computed and at most $m$ multiplications of two polynomials already computed: the $p$ for which a single evaluation scheme computes $p(X)$, for square matrices $X$ of every size, with at most $m$ matrix–matrix multiplications and otherwise only sums and scalar multiples of matrices already computed. For $0 < \delta < 1$ let $I_\delta = [-1, -\delta] \cup [\delta, 1]$ and $$E_m(\delta) = \inf_{p \in \mathcal P_m} \max_{x \in I_\delta} |p(x) - \operatorname{sign}(x)|.$$ Amsel et al. ask how this error behaves asymptotically, motivated by approximating the matrix sign function of a symmetric matrix with eigenvalues in $I_\delta$ using only matrix multiplications, which dominate the cost, and matrix additions and scalings. Every polynomial in $\mathcal P_m$ has degree at most $2^m$, and Paterson and Stockmeyer showed that every polynomial of degree $n$ lies in $\mathcal P_m$ for some $m = O(\sqrt n)$. Eremenko and Yuditskii found the exact asymptotics, as $n \to \infty$ with $\delta$ fixed, of the least uniform deviation from $\operatorname{sign}$ on $I_\delta$ of a real polynomial of degree at most $n$.
Problem. Determine matching asymptotic upper and lower bounds for $E_m(\delta)$, with the dependence on both $m$ and $\delta$ explicit.
Source: Amsel et al. (2026), Problem 6.3; made precise by OpenProblemsInNLA (real polynomials computed by straight-line programs from 1 and x, and an infimum where Amsel et al. write a minimum).
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- CA
- Keywords
- matrix polynomials, matrix sign function, OpenProblemsInNLA, polynomial approximation
- Literature checked
- Oct. 7, 2026 by clemens-admin
References
@misc{amsel2026,
author = {Amsel, Noah and Baumann, Yves and Beckman, Paul and B{\"u}rgisser, Peter and Cama{\~n}o, Chris and Chen, Tyler and Chow, Edmond and Damle, Anil and Derezinski, Michal and Embree, Mark and Epperly, Ethan N. and Falgout, Robert and Fornace, Mark and Greenbaum, Anne and Greif, Chen and Halikias, Diana and Huang, Zhen and Jarlebring, Elias and Koutis, Yiannis and Kressner, Daniel and Kyng, Rasmus and Liesen, J{\"o}rg and Lok, Jackie and Meyer, Raphael A. and Nakatsukasa, Yuji and Pearce, Kate and Peng, Richard and Persson, David and Rebrova, Eliza and Schneider, Ryan and Shah, Rikhav and Solomonik, Edgar and Srivastava, Nikhil and Townsend, Alex and Webber, Robert J. and Williams, Jess},
title = {Linear Systems and Eigenvalue Problems: Open Questions from a {S}imons Workshop},
year = {2026},
eprint = {2602.05394},
archivePrefix = {arXiv},
}
@article{paterson1973,
author = {Paterson, Michael S. and Stockmeyer, Larry J.},
title = {On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials},
journal = {SIAM J. Comput.},
volume = {2},
number = {1},
year = {1973},
pages = {60--66},
doi = {10.1137/0202007},
}
@article{eremenko2007,
author = {Eremenko, Alexandre and Yuditskii, Peter},
title = {Uniform approximation of sgn $x$ by polynomials and entire functions},
journal = {J. Anal. Math.},
volume = {101},
number = {1},
year = {2007},
pages = {313--324},
doi = {10.1007/s11854-007-0011-3},
eprint = {math/0604324},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-mf01,
author = {Townsend, Alex},
title = {{MF-01}: Optimal sign approximation with a multiplication budget},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/matrix-functions-and-stability/MF-01/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00160, "Optimal sign approximation with a multiplication budget", clopen.solutions.