Smith form computation : State of the art

Elimination with gcd : [Smith]

• [Kannan-Bachem 1979]

• Integers modulo a polynomial bound on the determinant

• [Iliopoulos 1989]

• O( s5 I(s2) ), s = m+n+log||A||

• [Storjohan 1996]

• O~( m2n I(n log||A||) )

Iterative techniques : Blackbox

• [Giesbrecht 1996]

• Probabilistic, Monte-Carlo

• More suited to sparse computation

• O(m2log||A||) Blackbox evaluations

+ O(m2n log||A||) additional bit op.

Diapositive précédente

Diapositive suivante

Revenir à la première diapositive

Afficher la version graphique