Export Citations
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- research-articleJuly 2014
Algebraic complexity theory and matrix multiplication
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPage 23https://doi.org/10.1145/2608628.2627493This tutorial will give an overview of algebraic complexity theory focused on bilinear complexity, and describe several powerful techniques to analyze the complexity of computational problems from linear algebra, in particular matrix multiplication. The ...
- research-articleJuly 2014
Linear independence oracles and applications to rectangular and low rank linear systems
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 381–388https://doi.org/10.1145/2608628.2608673Randomized algorithms are given for linear algebra problems on an input matrix A ∈ Knxm over a field K. We give an algorithm that simultaneously computes the row and column rank profiles of A in 2r3 + (r2 + n + m + |A|)1+o(1) field operations from K, ...
- research-articleJuly 2014
Powers of tensors and fast matrix multiplication
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 296–303https://doi.org/10.1145/2608628.2608664This paper presents a method to analyze the powers of a given trilinear form (a special kind of algebraic construction also called a tensor) and obtain upper bounds on the asymptotic complexity of matrix multiplication. Compared with existing approaches,...
- research-articleJuly 2014
Online order basis algorithm and its impact on the block Wiedemann algorithm
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 202–209https://doi.org/10.1145/2608628.2608647Order bases are a fundamental tool for linear algebra with polynomial coefficients. In particular, block Wiedemann methods are nowadays able to tackle large sparse matrix problems because they benefit from fast order basis algorithms. However, such fast ...
- research-articleJuly 2014
LLL reducing with the most significant bits
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic ComputationPages 367–374https://doi.org/10.1145/2608628.2608645Let B be a basis of a Euclidean lattice, and B an approximation thereof. We give a sufficient condition on the closeness between B and B so that an LLL-reducing transformation U for B remains valid for B. Further, we analyse an efficient reduction ...