Nearly Optimal Sparse Polynomial Multiplication
| Autor: | Vasileios Nakos |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Symbolic Computation Fast Fourier transform 020206 networking & telecommunications 02 engineering and technology Symbolic Computation (cs.SC) Library and Information Sciences Data structure Computer Science Applications Convolution Combinatorics Set (abstract data type) Product (mathematics) Computer Science - Data Structures and Algorithms ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) Multiplication Sparse polynomial Information Systems Mathematics |
| Zdroj: | IEEE Transactions on Information Theory. 66:7231-7236 |
| ISSN: | 1557-9654 0018-9448 |
| DOI: | 10.1109/tit.2020.2989385 |
| Popis: | In the sparse polynomial multiplication problem, one is asked to multiply two sparse polynomials f and g in time that is proportional to the size of the input plus the size of the output. The polynomials are given via lists of their coefficients F and G, respectively. Cole and Hariharan (STOC 02) have given a nearly optimal algorithm when the coefficients are positive, and Arnold and Roche (ISSAC 15) devised an algorithm running in time proportional to the "structural sparsity" of the product, i.e. the set supp(F)+supp(G). The latter algorithm is particularly efficient when there not "too many cancellations" of coefficients in the product. In this work we give a clean, nearly optimal algorithm for the sparse polynomial multiplication problem. Accepted to IEEE Transactions on Information Theory |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|