Name
Abstract | ||
|---|---|---|
The input to our algorithm is a multivariate polynomial, whose complex rational coefficients are considered imprecise with an unknown error that causes f to be irreducible over the complex numbers C. We seek to perturb the coefficients by a small quantitity such that the resulting polynomial factors over C. Ideally, one would like to minimize the perturbation in some selected distance measure, but no efficient algorithm for that is known. We give a numerical multivariate greatest common divisor algorithm and use it on a numerical variant of algorithms by W. M. Ruppert and S. Gao. Our numerical factorizer makes repeated use of singular value decompositions. We demonstrate on a significant body of experimental data that our algorithm is practical and can find factorizable polynomials within a distance that is about the same in relative magnitude as the input error, even when the relative error in the input is substantial (10-3). |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1145/1005285.1005311 | ISSAC |
Keywords | Field | DocType |
differential equation,numerical multivariate,multivariate polynomial,unknown error,input error,approximate factorization,efficient algorithm,complex rational coefficient,numerical variant,relative error,numerical factorizer,complex number,greatest common divisor algorithm,singular value decomposition,polynomial factorization,greatest common divisor | Discrete mathematics,Combinatorics,Polynomial,Square-free polynomial,Factorization of polynomials over finite fields,Greatest common divisor,Polynomial greatest common divisor,Dixon's factorization method,Irreducible polynomial,Mathematics,Factorization of polynomials | Conference |
ISBN | Citations | PageRank |
1-58113-827-X | 41 | 1.84 |
References | Authors | |
20 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shuhong Gao | 1 | 469 | 47.50 |
| Erich Kaltofen | 2 | 2332 | 261.40 |
| John P. May | 3 | 109 | 6.66 |
| Zhengfeng Yang | 4 | 350 | 23.43 |
| Lihong Zhi | 5 | 463 | 33.18 |