Algorithms for a Multiple Algebraic Extension
Lars Langemyr · Birkhäuser Boston eBooks · 1991
We give fast algorithms for computing product and inverse in a multiple algebraic extension of the rational numbers. The algorithms are almost linear in terms of the output length, i.e. they work in time O ( d 1+δ ), for all δ > 0, where d is an a priori bound on the length of the output. Since we require time Ω( d ) just to write down the output the algorithms are close to optimal. The algorithm for inverse uses a technique referred to as dynamic evaluation for computing in algebraic extensions defined by reducible polynomials. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.