Fast evaluation of polynomials by rational preparation. (English) Zbl 0238.12002
It is well known that by calculating beforehand certain auxiliary functions of the coefficients of a polynomial \(P\), every subsequent evaluation of \(P\) can be performed with about half the number of multiplications that would be otherwise required. However, the auxiliary functions involved were obtained from the coefficients of \(P\) by solving high-degreed algebraic equations. Here we show that near optimal results can be obtained by use of rational auxiliary functions. We develop a variety of such rational preparation schemes for a variety of problems.
Reviewer: Michael O. Rabin
MSC:
11Y16 | Number-theoretic algorithms; complexity |
68W30 | Symbolic computation and algebraic computation |
11R09 | Polynomials (irreducibility, etc.) |
11C08 | Polynomials in number theory |
Keywords:
number of additions and multiplications; evaluation of monic polynomials; preconditioning; solution of high-order algebraic equations; asymptotic results; polynomials in several variables; rational functions; matrix polynomialsReferences:
[1] | Belaga, Problemy Kibernet. 5 pp 7– (1961) |
[2] | The Art of Programming, Vol. 2, Addison-Wesley Pub. Co., 1969. |
[3] | Motzkin, Bulletin American Mathematical Society 61 pp 163– (1955) |
[4] | Pan, A.M.S. Russian Mathematical Surveys 21 pp 105– (1966) |
[5] | and , Bounds on the evaluation times for polynomials, Proc. of the 12 th IEEE Annual Symposium on Switching and Automata Theory, 1971, pp. 140–143. |
[6] | Winograd, Comm. Pure App. Math. 23 pp 165– (1970) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.