Loading…
An Improved Lower Bound on Polynomial Multiplication
We prove an asymptotic lower bound of 3.52n nonscalar multiplications for (degree n - 1 by degree n - 1) polynomial multiplication in a model which allows only integers as scalars. Index Terms-Algebraic complexity, lower bound, polynomial multiplication.
Saved in:
| Published in: | IEEE transactions on computers 1980-05, Vol.C-29 (5), p.337-340 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | We prove an asymptotic lower bound of 3.52n nonscalar multiplications for (degree n - 1 by degree n - 1) polynomial multiplication in a model which allows only integers as scalars. Index Terms-Algebraic complexity, lower bound, polynomial multiplication. |
|---|---|
| ISSN: | 0018-9340 1557-9956 |
| DOI: | 10.1109/TC.1980.1675583 |