# What algorithms does NSolve use?

I've been using NSolve to find roots, and now I've been wondering what underlying algorithm Mathematica uses. It's probably similar to FindRoot, so is it the Newton-Raphson method?

In class we've been told that it probably is a mix of the Newton-Raphson and the bisection methods.

• it must be documented somewhere here wolfram.com/learningcenter/tutorialcollection specifically here reference.wolfram.com/mathematica/tutorial/NDSolveOverview.html and most probably there reference.wolfram.com/mathematica/tutorial/… – chris May 1 '14 at 10:01
• For sparse linear systems, Solve and NSolve use several efficient numerical methods, mostly based on Gauss factoring with Markowitz products (approximately 250 pages of code). For systems of algebraic equations, NSolve computes a numerical Gröbner basis using an efficient monomial ordering, then uses eigensystem methods to extract numerical roots. See also Numerical Root Finding and Numerical Equation Solving. – Artes May 1 '14 at 11:05
• For univariate inputs NSolve calls the function NRoots. That in turn has a Method option. From the documentation for NRoots: Possible settings for the Method option include: "Aberth", "CompanionMatrix", and "JenkinsTraub". The methods mentioned in the post are good for finding an individual root (not necessarily of a polynomial) but not really meant for finding all polynomial roots. And bisection is only for real roots. – Daniel Lichtblau May 1 '14 at 14:21

In at least the univariate case, the guess of "Newton-Raphson" is not too far off. Daniel mentions the three possible methods supported by NSolve[]/NRoots[] in his comment.
"CompanionMatrix" is likely done by forming the Frobenius companion matrix from the polynomial's coefficients, and then performing the usual QR algorithm to extract the eigenvalues, so that is the odd one out. (There are more efficient structure-exploiting methods than vanilla QR (e.g. this), and other possible companion matrices (e.g. this), but it doesn't seem to me that these specializations are exploited.)