2

I am currently beginning a long term investigation (I will have 6 months of time). I wish to better understand fundamental properties of polynomials and eventually come up with a good root finding algorithm.

I really almost know nothing advanced about the subject. But anyhow, I have considered studying towards these four areas:

1 - Learn about field theory and abstract/advance my knowledge about polynomials

2 - learn about existing algorithms - (bracketing and open methods)

3 - some basic abstract algebra (Galois) - group theory

4 - learn about basic complexity theory and be able to analyze algorithms for their efficiency

SO, my question: What are some books and sources you guys recommend, where I can begin my study. Additionally, are my goals feasible or should I redirect my investigation (if you think there are better/more appropriate things to study)?

Do note, I am willing to spend lots of time and understand as much as possible, but my formal education in mathematics is not even at an undergraduate level (but I give it my best shot).

Just_a_fool
  • 2,256

3 Answers3

3

I think the newer versions of the "Numerical Recipes" book are pretty good, personally. The algorithms are not state-of-the art, but they are easy to understand, easy to use, and usually get the job done. A good place to start, certainly.

Root-finding is a very mature topic. People have been writing programs to do it for 50 years or more. So, I would guess that it will be difficult to make great progress. So, in that sense, not a very good research topic. On the other hand, if you do make good progress, then it will be very valuable, because root-finding is important in many areas.

If your goal is to eventually write a good root-finding algorithm, I would guess that abstract algebra (Galois theory and the like) will have limited value to you. But I could be wrong.

One idea is to look for new root-finding methods that are well-suited to highly parallel computer architectures (like GPUs, for example). This does not have a long history, so there might still be a lot of areas left to explore, and progress might be easier.

bubba
  • 43,483
  • 3
  • 61
  • 122
1

"Numerical Recipes in C" is terrible. (Many bugs. Horrific mix of 0-based and 1-based arrays. Many bugs.) Start there. For root-finding, the algorithms and motivations are well explained. ("Numerical Recipes: The Art of Scientific Computing" may be better, but I have no experience with it.)

If you can make sense of that, start digging through the see-alsos and references at Root-finding algorithm.

Eric Towers
  • 67,037
1

For the Galois Theory/polynomial algorithms part, I suggest Dummit & Foote's Abstract algebra ; chapter 13 and 14 give a good overview of this theory, and you can look at section 9.6 for a detailed explanation on Gröbner bases, which eventually leads to elimination theory.

If your algebra is not good enough, you'll also find group theory, ring theory, and lots of explanations/exercises about principal ideal domains and euclidean domains, and the properties of these two are the main ideas behind polynomial tricks.

Hope that helps,

Patrick Da Silva
  • 41,413