Paper Info
Title
Recent progress in linear algebra and lattice basis reduction
Abstract
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.
Year
DOI
Venue
2011
10.1145/1993886.1993889
ISSAC
Keywords
DocType
Citations 
basis reduction algorithm,fundamental linear algebra problem,lll reduction,lattice basis reduction,basis reduction,integer basis reduction,general goal,complexity estimate,basic tool,integer matrix multiplication,recent progress,matrix multiplication,linear algebra,polynomial matrix
Conference
0
PageRank 
References 
Authors
0.34
9
1
Name
Order
Citations
PageRank
Gilles Villard156548.04