Efficient Evaluation of Large Polynomials
Minimizing the evaluation cost of a polynomial expression is a fundamental problem in computer science. We propose tools that, for a polynomial P given as the sum of its terms, compute a representation that permits a more efficient evaluation. Our algorithm runs in d(nt) [superscript O(1)] bit opera...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90262 |
| _version_ | 1826200970636296192 |
|---|---|
| author | Leiserson, Charles E. Li, Liyun Maza, Marc Moreno Xie, Yuzhen |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Leiserson, Charles E. Li, Liyun Maza, Marc Moreno Xie, Yuzhen |
| author_sort | Leiserson, Charles E. |
| collection | MIT |
| description | Minimizing the evaluation cost of a polynomial expression is a fundamental problem in computer science. We propose tools that, for a polynomial P given as the sum of its terms, compute a representation that permits a more efficient evaluation. Our algorithm runs in d(nt) [superscript O(1)] bit operations plus dt [superscript O(1)] operations in the base field where d, n and t are the total degree, number of variables and number of terms of P. Our experimental results show that our approach can handle much larger polynomials than other available software solutions. Moreover, our computed representation reduce the evaluation cost of P substantially. |
| first_indexed | 2024-09-23T11:44:35Z |
| format | Article |
| id | mit-1721.1/90262 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:44:35Z |
| publishDate | 2014 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/902622022-10-01T05:39:55Z Efficient Evaluation of Large Polynomials Leiserson, Charles E. Li, Liyun Maza, Marc Moreno Xie, Yuzhen Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Leiserson, Charles E. Minimizing the evaluation cost of a polynomial expression is a fundamental problem in computer science. We propose tools that, for a polynomial P given as the sum of its terms, compute a representation that permits a more efficient evaluation. Our algorithm runs in d(nt) [superscript O(1)] bit operations plus dt [superscript O(1)] operations in the base field where d, n and t are the total degree, number of variables and number of terms of P. Our experimental results show that our approach can handle much larger polynomials than other available software solutions. Moreover, our computed representation reduce the evaluation cost of P substantially. 2014-09-22T17:14:55Z 2014-09-22T17:14:55Z 2010-09 Article http://purl.org/eprint/type/JournalArticle 978-3-642-15581-9 978-3-642-15582-6 0302-9743 1611-3349 http://hdl.handle.net/1721.1/90262 Leiserson, Charles E., Liyun Li, Marc Moreno Maza, and Yuzhen Xie. "Efficient Evaluation of Large Polynomials." K. Fukuda et al. (Eds.): Mathematical Software – ICMS 2010, Lecture Notes in Computer Science, Volume 6327, 2010, pp. 342-353. en_US http://dx.doi.org/10.1007/978-3-642-15582-6_55 Mathematical Software – ICMS 2010 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag Other univ. web domain |
| spellingShingle | Leiserson, Charles E. Li, Liyun Maza, Marc Moreno Xie, Yuzhen Efficient Evaluation of Large Polynomials |
| title | Efficient Evaluation of Large Polynomials |
| title_full | Efficient Evaluation of Large Polynomials |
| title_fullStr | Efficient Evaluation of Large Polynomials |
| title_full_unstemmed | Efficient Evaluation of Large Polynomials |
| title_short | Efficient Evaluation of Large Polynomials |
| title_sort | efficient evaluation of large polynomials |
| url | http://hdl.handle.net/1721.1/90262 |
| work_keys_str_mv | AT leisersoncharlese efficientevaluationoflargepolynomials AT liliyun efficientevaluationoflargepolynomials AT mazamarcmoreno efficientevaluationoflargepolynomials AT xieyuzhen efficientevaluationoflargepolynomials |