2

Based on this question, there's an efficient algorithm to determine whether a quadratic multivariate polynomial has a root.

What are some algorithms to enumerate these solutions? I'm interested in rational roots (working in $\mathbb{Q}$), if possible, or roots over the real numbers or some subfield of the real numbers if not. I'd like algorithms that are as efficient as possible.

In the case of a large set of solutions (e.g. exponentially or infinitely large), an algorithm whose running time is polynomial in the number of roots would be ideal.

Community
  • 1
Joe
  • 139
  • 4
  • Please specify more about your problem. What field are you working over? Are you looking at enumerating the solutions to a single quadratic polynomial, or a system of such equations? What can you tell us about the typical range of parameters you are interested in? The critical parameters include $n$ (the number of variables) and $\mathbb{F}$ (the field you are working in). Also, you should be aware that the number of solutions can be huge, so it might not be possible to explicitly list them all in polynomial time. So, do you care about the algorithm's running time? – D.W. Dec 09 '13 at 03:03
  • Thanks for the comment, @D.W. The most important thing is the running time. So while I'd be interested in a system of equations, just one like in the linked question is fine. n can be any number > 2 and the order of the polynomial is always quadratic. All solutions should be over the rationals. Or the reals (or some subfield of the reals) if that's not feasible. – Joe Dec 09 '13 at 03:15
  • 1
    Thanks, @Joe. Some etiquette for this site: when responding to requests for clarifications, we like you to edit your original question to add those clarifications to the question, so people don't need to read the comments to understand the problem. I've done that for you this time. Separately: I noticed you didn't respond to my comment that the set of solutions could be large (e.g., infinitely large; or exponentially large). What were you thinking ought to be done about that? Are you looking for an algorithm whose running time is polynomial in the number of roots, or something like that? – D.W. Dec 09 '13 at 04:00
  • Thanks, @D.W. and for the edits. I'll do that next time. As for the large solutions, "running time is polynomial in the number of roots" is perfect. I'll update the question. – Joe Dec 14 '13 at 21:44

0 Answers0