Talk:Polynomial root-finding

companion matrix methods

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

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]

Hi! I am new to wiki. I am planning to edit this page by writing a general overview based on your suggestions, which should be done within 1 week.

Meanwhile, I also want to add a section on machines designed for root-finding starting from mid-19th century, recollecting relevant work of F. Bushforth, Russell, Tower. Lzxwuw (talk) 22:57, 28 April 2025 (UTC)[reply]

Section § Principles, is already an overview, and the article itself is intended also as an overview. It seems that your project is to write a new section from scratch. Instead, it seems better to process incrementally by discussing first the issues of the current version in this talk page, and then fixing them one after the other.

I may have misunderstood your project. In this case, before implenting in the article, it could be useful to give more details. Indeed, Wikipedia is a collaborative project, and major edits of the article require a WP:CONSENSUS among interested editors. D.Lazard (talk) 01:24, 29 April 2025 (UTC)[reply]

@Lzxwuw with that said though, you can definitely boldly add or remove sections, add significant text, rearrange existing material, move content between articles, etc., if you think those are improvements. If your changes are controversial they might get reverted (the article returned to its previous state) or reworked, and then editors who disagree can discuss. –jacobolus (t) 02:05, 29 April 2025 (UTC)[reply]

Hi! I have posted an editing plan in the talk, replying to Prof D.Lazard. I will gratefully wait for suggestions from both of you before any actual editions. Lzxwuw (talk) 03:58, 29 April 2025 (UTC)[reply]

I see! Thanks for the clarification. I am suggesting to:

(i) Add a section on Historical Overview, to explain the history of polynomial root-finding. I feel that this article would benefit from the Historical Overview, as it now only contains descriptions of numerical methods. I plan to extract the relevant info from the first two pages of Pan Victor Y's article attached above.

(ii) modify the principles section by dividing it to the following subsections, to improve clarity:

1.Motivation for numerical methods: In this subsection, the nonexistence of a radical solution of deg >=5 polynomials should be explained, as well as the complexity of the root formulas of cubics and quartics. This should inform readers who know little about the area why all algorithms aim at numerical solutions.

2. Type of Root Finding problems In this subsection, the different types of root solving problems are discussed (finding one real root, finding all real roots, find all complex solutions, find complex solutions in a certain domain on the complex plane... However, contrary to the current entry, I propose to only state that for different types of root solving problems, different algorithms are implemented. The specific algorithms for each case, and the explanation of Newton's algorithm not suitable for finding all real roots, etc, should be deferred to later sections for clarity.

//////////////////

I am not an expert on Polynomial root-finding algorithms; my knowledge is no more than the theoretical results from Galois theory, and the Newton's method. Thus, I will not make any mathematical editions on the numerical algorithms.

////////

Please tell me your suggestions on the editing plan! I really appreciate your patience. Lzxwuw (talk) 03:54, 29 April 2025 (UTC)[reply]

I mostly agree with this project. However, see my comment in § Section "Principles"

Instead of section title, "Historical Overview", I suggest the more common section name "History". For clarity I suggest also to split it into several subsections: "Algebraic methods", from antiquity (quadratic formula) to Abel–Ruffini theorem and Galois theory; "Real-root isolation", starting from Descartes' rule of signs; and "Numeral methods", starting from Newton and the fundamental theorem of algebra (which validate these methods). This History section could also include a section "Root-finding machines" D.Lazard (talk) 11:14, 29 April 2025 (UTC)[reply]

This sounds wonderful. I have commited some initial changes. I know relatively well the history of algebraic methods. I know little about real-root isolation and most numeral methods. For the first part, I can attempt to write a condensed version of the wikipage. For the numeral methods, I know no more than Newton's method and fundamental thm of algebra. I will remark on them and leave it for future editions. Lzxwuw (talk) 00:46, 30 April 2025 (UTC)[reply]

Section "Numerical computation of multiple roots"

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"

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]

As there is no principle in this section, I renamed it § Overview. Nevertheless, I agree that this section deserves to be rewritten, with some parts moved in the (too short) lead, and some parts moved in a lacking History section. D.Lazard (talk) 10:52, 29 April 2025 (UTC)[reply]

Section "Historical Development of Mechanical Root-Finding Methods"

Around mid-late 19th century, there are algorithms proposed by Bushforth, Russell, Tower,... on building machines that solves the real roots of polynomials numerically. I am not sure if it fits into this Article, or probably I should create a new Article on wiki explaining the relevant developments. Lzxwuw (talk) 04:05, 29 April 2025 (UTC)[reply]