Balanced dense polynomial multiplication on multi-cores
In symbolic computation, polynomial multiplication is a fundamental operation akin to matrix multiplication in numerical computation. We present efficient implementation strategies for FFT-based dense polynomial multiplication targeting multi-cores. We show that balanced input data can maximize para...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Online Access: | http://hdl.handle.net/1721.1/59993 |
| _version_ | 1811072330793746432 |
|---|---|
| author | Xie, Yuzhen Maza, Marc Moreno |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Xie, Yuzhen Maza, Marc Moreno |
| author_sort | Xie, Yuzhen |
| collection | MIT |
| description | In symbolic computation, polynomial multiplication is a fundamental operation akin to matrix multiplication in numerical computation. We present efficient implementation strategies for FFT-based dense polynomial multiplication targeting multi-cores. We show that balanced input data can maximize parallel speedup and minimize cache complexity for bivariate multiplication. However, unbalanced input data, which are common in symbolic computation, are challenging. We provide efficient techniques, what we call contraction and extension, to reduce multivariate (and univariate) multiplication to balanced bivariate multiplication. Our implementation in Cilk++ demonstrates good speedup on multi-cores. |
| first_indexed | 2024-09-23T09:04:17Z |
| format | Article |
| id | mit-1721.1/59993 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:04:17Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/599932022-09-30T13:13:22Z Balanced dense polynomial multiplication on multi-cores Xie, Yuzhen Maza, Marc Moreno Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Xie, Yuzhen Xie, Yuzhen In symbolic computation, polynomial multiplication is a fundamental operation akin to matrix multiplication in numerical computation. We present efficient implementation strategies for FFT-based dense polynomial multiplication targeting multi-cores. We show that balanced input data can maximize parallel speedup and minimize cache complexity for bivariate multiplication. However, unbalanced input data, which are common in symbolic computation, are challenging. We provide efficient techniques, what we call contraction and extension, to reduce multivariate (and univariate) multiplication to balanced bivariate multiplication. Our implementation in Cilk++ demonstrates good speedup on multi-cores. Natural Sciences and Engineering Research Council of Canada (NSERC) Networks of Centres of Excellence (Canada) MITACS (Network) 2010-11-17T15:04:00Z 2010-11-17T15:04:00Z 2010-02 2009-12 Article http://purl.org/eprint/type/ConferencePaper 978-0-7695-3914-0 INSPEC Accession Number: 11141569 http://hdl.handle.net/1721.1/59993 Maza, M.M., and Yuzhen Xie. “Balanced Dense Polynomial Multiplication on Multi-Cores.” Parallel and Distributed Computing, Applications and Technologies, 2009 International Conference on. 2009. 1-9. ©2010 IEEE. en_US http://dx.doi.org/10.1109/PDCAT.2009.87 International Conference on Parallel and Distributed Computing, Applications and Technologies, 2009 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Xie, Yuzhen Maza, Marc Moreno Balanced dense polynomial multiplication on multi-cores |
| title | Balanced dense polynomial multiplication on multi-cores |
| title_full | Balanced dense polynomial multiplication on multi-cores |
| title_fullStr | Balanced dense polynomial multiplication on multi-cores |
| title_full_unstemmed | Balanced dense polynomial multiplication on multi-cores |
| title_short | Balanced dense polynomial multiplication on multi-cores |
| title_sort | balanced dense polynomial multiplication on multi cores |
| url | http://hdl.handle.net/1721.1/59993 |
| work_keys_str_mv | AT xieyuzhen balanceddensepolynomialmultiplicationonmulticores AT mazamarcmoreno balanceddensepolynomialmultiplicationonmulticores |