The Library
Practical polynomial factoring in polynomial time
Tools
Hart, William B., Hoeij, Mark van and Novocin, Andrew (2011) Practical polynomial factoring in polynomial time. In: ISSAC '11 International Symposium on Symbolic and Algebraic Computation (co-located with FCRC 2011), San Jose, CA, 7-11 Jun 2011. Published in: Proceedings of the 36th international symposium on Symbolic and algebraic computation pp. 163-170. doi:10.1145/1993886.1993914 ISSN 9781450306751.
|
Text
WRAP_Hart_0584144-ma-270913-poly_factor.pdf - Accepted Version Download (566Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/1993886.1993914
Abstract
State of the art factoring in Q[x] is dominated in theory by a combinatorial reconstruction problem while, excluding some rare polynomials, performance tends to be dominated by Hensel lifting. We present an algorithm which gives a practical improvement (less Hensel lifting) for these more common polynomials. In addition, factoring has suffered from a 25 year complexity gap because the best implementations are much faster in practice than their complexity bounds. We illustrate that this complexity gap can be closed by providing an implementation which is comparable to the best current implementations and for which competitive complexity results can be proved.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Algorithms | ||||
Journal or Publication Title: | Proceedings of the 36th international symposium on Symbolic and algebraic computation | ||||
Publisher: | ACM | ||||
ISSN: | 9781450306751 | ||||
Book Title: | Proceedings of the 36th international symposium on Symbolic and algebraic computation - ISSAC '11 | ||||
Official Date: | 2011 | ||||
Dates: |
|
||||
Page Range: | pp. 163-170 | ||||
DOI: | 10.1145/1993886.1993914 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 20 December 2015 | ||||
Date of first compliant Open Access: | 20 December 2015 | ||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC) , National Science Foundation (U.S.) (NSF) | ||||
Grant number: | EP/G004870/1 (EPSRC) ; 0728853, 1017880 (NSF) | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | ISSAC '11 International Symposium on Symbolic and Algebraic Computation (co-located with FCRC 2011) | ||||
Type of Event: | Conference | ||||
Location of Event: | San Jose, CA | ||||
Date(s) of Event: | 7-11 Jun 2011 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year