Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question
    
This might be relevant in Computer Science too. –  vonbrand Mar 3 at 10:05

3 Answers 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.

share|improve this answer

"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.

share|improve this answer

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,

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.