Symbolic Computation Group
David R. Cheriton School of Computer Science
|
|
|
Friday, March 9, 2012, at U. of Waterloo Relaxed Hensel lifting for algebraic systems Romain Lebreton, Ecole Polytechnique, Paris, France Abstract : This talk focus on the Hensel lifting of a root of an algebraic system. Although Hensel lifting is valid for any p-adic ring, we will for the sake of simplicity work with the power series ring. Classically, we would use the Newton operator to lift a regular root of an algebraic system. This way, we double the precision of the power series at each step until the precision suits our need. This method costs roughly an inversion of the Jacobian matrix and an evaluation of the system at the lifted root. We present another method that do not pay the cost of the inversion of the Jacobian matrix. In return, we have a logarithmic overhead in the precision at which we lift the power series. After recalling the lazy representation of power series, I will explain the relaxed multiplication, which is quasi-optimal. Then I will present our algorithms in the relaxed representation to lift a solution of a univariate polynomial, a linear system and finally an algebraic system. I will give some timings of our implementation in the computer algebra software Mathemagix and compare then with the Newton iteration, Linbox and IML. This is a joint work with Jeremy Berthomieu.
|
Last modified on Wednesday, 07 November 2012, at 12:10 hours.