NC 2 computation of gcd-free basis and application to parallel algebraic numbers computation
Thierry Gautier, Jean-Louis Roch · 1997
We establish that the problem of computing a gcd-free basis for a set of polynomials is in AfC~for any arbitrary field F. This leads to a proof that arithmetic for a simple algebraic extension is in [email protected] result is applied to improve the complexity of the parallel deterministic algorithm to compute the Jordan normal form of a n dimensional matrix in time 0(log2 n).PA.S(.'0 97 Wailea, Maui, Hawaii.USA 0-89791-95l-3/97i7Our algorithm proves that the problem is in [email protected] result is applied to algebraic number computation in a parallel D5 arithmetic manner.A parallel model of computation is presented and we give bounds on the complexity of simulating it with PRAM arithmetic over a field F. We conclude this paper by reviewing result on computing Jordan normal form and we demonstrate that this problem is in Ncj. Fast Gcd-l%e Basis ComputationsLet F be an arbitrary commutative field.The computational model used in this section is the arithmetic PRAM model.We say that a problem lies in NC! [4, 11] if there exists a parallel algorithm which solves it in time is bounded by O(log~n) using nQ1) processors for all inputs of size n. 2.1