Jump to content

Talk:Polynomial root-finding algorithms

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

companion matrix methods

[edit]

I am not remotely an expert here, but my vague impression is that companion matrix methods are used widely in practice (e.g. built into Matlab). There should probably be some description of how that works, rather than just a mention. (Otherwise this article as it stands looks sort of like a vehicle for promoting Zhonggang Zeng and his work, rather than a general encyclopedia article.) A google scholar search for 'companion matrix roots' turns up some widely cited papers that look relevant, for instance:

Edelman, Alan, and H. Murakami. "Polynomial roots from companion matrix eigenvalues". Mathematics of Computation 64, no. 210 (1995): 763-776.
Toh, Kim-Chuan, and Lloyd N. Trefethen. "Pseudozeros of polynomials and pseudospectra of companion matrices". Numerische Mathematik 68, no. 3 (1994): 403-425.
Boyd, John P. "Finding the zeros of a univariate equation: proxy rootfinders, Chebyshev interpolation, and the companion matrix". SIAM review 55, no. 2 (2013): 375-396.
Aurentz, Jared L., Thomas Mach, Raf Vandebril, and David S. Watkins. "Fast and backward stable computation of roots of polynomials". SIAM Journal on Matrix Analysis and Applications 36, no. 3 (2015): 942-973.

jacobolus (t) 18:22, 28 January 2023 (UTC)[reply]

While we are at it, the word 'basis' does not appear anywhere in this article. In many (most?) practical settings polynomials are expressed in the Bernstein basis, a Lagrange interpolating basis, Chebyshev basis, or similar, rather than the monomial basis. This article should discuss how the choice of polynomial basis affects the algorithms used for rootfinding.

Some more papers that look relevant:

Day, David, and Louis Romero. "Roots of polynomials expressed in terms of orthogonal polynomials". SIAM journal on numerical analysis 43, no. 5 (2005): 1969-1987.
Noferini, Vanni, and Javier Pérez. "Chebyshev rootfinding via computing eigenvalues of colleague matrices: when is it stable?" Mathematics of Computation 86, no. 306 (2017): 1741-1767.
Lawrence, Piers W., and Robert M. Corless. "Stability of rootfinding for barycentric Lagrange interpolants". Numerical Algorithms 65 (2014): 447-464.
Roy, Marie-Françoise. "The Bernstein basis and real root isolation". Combinatorial and computational geometry 52 (2005): 459.
Spencer, Melvin R. Polynomial Real root finding in Bernstein form. Brigham Young University, 1994.

jacobolus (t) 18:28, 28 January 2023 (UTC)[reply]

General overviews of polynomial rootfinding

[edit]

This paper looks like it provides some good basic overview and historical discussion up through the mid 1990s:

Pan, Victor Y. "Solving a polynomial equation: some history and recent progress". SIAM review 39, no. 2 (1997): 187-220.

There is also a nice looking overview in:

Yap, Chee-Keng. "6. Roots of Polynomials". Fundamental problems of algorithmic algebra. Oxford University Press, 2000. Preliminary version available from Yap's website.

jacobolus (t) 18:56, 28 January 2023 (UTC)[reply]

Section "Numerical computation of multiple roots"

[edit]

Currently only cites a primary source, which should be avoided; citing a textbook or survey article would be better. fgnievinski (talk) 00:58, 12 March 2023 (UTC)[reply]

Section "Principles"

[edit]

Is the longest in the article. Based on its title, it's supposed to be short. It could have at least subsections. Or the lead, which is currently too short, could absorb some content from this section. fgnievinski (talk) 01:01, 12 March 2023 (UTC)[reply]

So go rewrite it if you want, or propose some concrete changes here on the talk page. Anyone with eyes can see that this section is long and kind of disorganized. Throwing an eyesore banner there doesn’t accomplish anything, especially if not accompanied by discussion. In my experience these banners get stuck into random parts of pages and then linger there for years, neither helping readers nor causing any productive action. –jacobolus (t) 01:07, 12 March 2023 (UTC)[reply]