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 (colocated with FCRC 2011), San Jose, CA, 711 Jun 2011. Published in: Proceedings of the 36th international symposium on Symbolic and algebraic computation pp. 163170.

Text
WRAP_Hart_0584144ma270913poly_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 > 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 
Page Range:  pp. 163170 
Identification Number:  10.1145/1993886.1993914 
Status:  Peer Reviewed 
Publication Status:  Published 
Access rights to Published version:  Restricted or Subscription Access 
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 (colocated with FCRC 2011) 
Type of Event:  Conference 
Location of Event:  San Jose, CA 
Date(s) of Event:  711 Jun 2011 
References:  [1] J. Abbott Bounds on Factors in Z[x] arXiv:0904.3057 
URI:  http://wrap.warwick.ac.uk/id/eprint/43600 
Request changes or add full text files to a record
Actions (login required)
View Item 
Downloads
Downloads per month over past year