Recent progress in linear algebra and lattice basis reduction (invited)

Gilles Villard (1, 2)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 ARENAIRE - Computer arithmetic

A general goal concerning fundamental linear algebra problems is to reduce the complexity estimates to essentially the same as that of multiplying two matrices (plus possibly a cost related to the input and output sizes). Among the bottlenecks one usually finds the questions of designing a recursive approach and mastering the sizes of the intermediately computed data. In this talk we are interested in two special cases of lattice basis reduction. We consider bases given by square matrices over K[x] or Z, with, respectively, the notion of reduced form and LLL reduction. Our purpose is to introduce basic tools for understanding how to generalize the Lehmer and Knuth-Schönhage gcd algorithms for basis reduction. Over K[x] this generalization is a key ingredient for giving a basis reduction algorithm whose complexity estimate is essentially that of multiplying two polynomial matrices. Such a problem relation between integer basis reduction and integer matrix multiplication is not known. The topic receives a lot of attention, and recent results on the subject show that there might be room for progressing on the question.

Mots clés: lattice basis reduction; column reduction; integer matrix; matrix polynomial; LLL; computational complexity; bit complexity

Domaines: Algorithme et structure de données [cs.DS]; Analyse numérique [cs.NA]; Calcul formel [cs.SC]; Complexité [cs.CC]

Gilles Villard. Recent progress in linear algebra and lattice basis reduction (invited). ISSAC'11 - International symposium on Symbolic and algebraic computation, 2011, San Jose, United States. pp.3-4, ⟨10.1145/1993886.1993889⟩. ⟨hal-00644796⟩