Multiplication overhead of cubic sign compositions
For $0 < \delta < 1$ let $I_\delta = [-1, -\delta] \cup [\delta, 1]$. 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. Let $$E_m(\delta) = \inf_{p \in \mathcal P_m} \max_{x \in I_\delta} |p(x) - \operatorname{sign}(x)|,$$ and for an integer $T \ge 0$ let $$C_T(\delta) = \inf_{a_t, b_t \in \mathbb{R}} \max_{x \in I_\delta} \bigl|(q_T \circ \cdots \circ q_1)(x) - \operatorname{sign}(x)\bigr|, \qquad q_t(x) = a_t x + b_t x^3,$$ where the empty composition ($T = 0$) is $x$. Amsel et al. ask how much extra work restricting to such compositions costs, 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. Each stage $q_t$ can be applied to a matrix with two matrix multiplications, so every composition of $T$ stages lies in $\mathcal P_{2T}$.
Problem. Determine the asymptotic dependence on $m$ and $\delta$ of $$T_{\min}(m, \delta) = \inf\{T \in \mathbb{N}_0 : C_T(\delta) \le E_m(\delta)\},$$ where $\inf \varnothing = +\infty$.
Source: Stated by OpenProblemsInNLA, after Amsel et al. (2026), Problem 6.5, which asks how the best error of compositions of T odd cubic polynomials compares with the best error using 2T matrix multiplications, or for the smallest T, as a function of m, at which it is at most the best error using m.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- CA
- Keywords
- matrix sign function, OpenProblemsInNLA, polynomial approximation, polynomial compositions
- Literature checked
- Oct. 8, 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},
}
@misc{openproblemsinnla-mf02,
author = {Townsend, Alex},
title = {{MF-02}: Multiplication overhead of cubic sign compositions},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/matrix-functions-and-stability/MF-02/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For $0 < \delta < 1$, the note compares compositions of odd cubic polynomials $a x + b x^3$ with arbitrary real polynomials computed from $1$ and $x$ with at most $m$ multiplications, as approximations of $\operatorname{sign}(x)$ on $[-1, -\delta] \cup [\delta, 1]$. It proves that the least number $T_{\min}(m, \delta)$ of cubic stages whose best error is at most …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00230, "Multiplication overhead of cubic sign compositions", clopen.solutions.