Name
Abstract | ||
|---|---|---|
This paper presents an improved adaptive hybrid algorithm for multiplying dense multivariate polynomials that is both time and space efficient. The hybrid algorithm makes use of two families of univariate algorithms, one Karatsuba based and the other DFT based, which are applied recursively to solve the multivariate problem. The hybrid algorithm is adaptive in that particular univariate algorithms are selected at run time to minimize the time complexity; an order-of-magnitude speedup with respect to classical multiplication is achieved over the entire practical range except for very small problems. Empirical investigation shows that most of the theoretical superiority is maintained in actual implementation. The largest contribution to the space requirements of the total algorithm is determined by the univariate algorithm used for the outermost variable; except for quite small problems, selecting univariate algorithms to minimize run time almost always leads to situations where the space requirements of the total algorithm are extremely close to the space required merely to store the result. |
Year | DOI | Venue |
|---|---|---|
1987 | 10.1145/23002.27646 | ACM Trans. Math. Softw. |
Keywords | Field | DocType |
general terms: algorithms,dense multivariate polynomial,small problem,improved adaptive hybrid algorithm,space requirement,time complexity,hybrid algorithm,particular univariate algorithm,design additional key words and phrases: algorithm design strategies,total algorithm,run time,univariate algorithm,low-space algorithm,nonasymptotically fast algorithms,algorithm design,assessment,efficiency | Mathematical optimization,Hybrid algorithm,Ramer–Douglas–Peucker algorithm,Algorithmics,Nondeterministic algorithm,Algorithm,Univariate,Population-based incremental learning,Mathematics,Difference-map algorithm,Karatsuba algorithm | Journal |
Volume | Issue | ISSN |
13 | 1 | 0098-3500 |
Citations | PageRank | References |
2 | 0.43 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vangalur S. Alagar | 1 | 164 | 39.10 |
| David K. Probst | 2 | 103 | 29.79 |