Keywords:
algebraic computations, linear algebra, algorithmic complexity, verified computations, cryptology and codes
Introduction
This course presents theoretical and practical aspects of exact computations with an accent on high-performance modelling.
- How difficult is it to compute a determinant over Z?
- What about optimal complexities in linear algebra?
- Are asymptotic complexities useful in practice?
- How to augment or verify the precision of computations?
We will study a selection of recent algorithmic break-through in the domain as well as their use in the solution of various problems, like analysis of DNA sequences, pattern recognition, coding theory, etc.
The course will have the favor of students interested in algorithmic complexity theory as well as mathematical computations and applications.
None
- Arbitrary precison integer, polynomial and floating point arithmetics.
- Exact modelizations:
- Pattern analysis in DNA.
- Pseudo-random generators and the liryc poetry of troubadours.
- Algebraic topology (pattern recognition, molecular interactions).
- Combinatorics (graph isomorphism).
- Error correcting codes and fault tolerance.
- Cryptology (breaking RSA and the Discrete Logarithm).
- Exact Linear Algebra
- Dense matrices and Sparse/Structured/blackbox matrices
- Exact direct and iterative methods
- Liftings and rational reconstruction
- Adaptive algorithms and international library LinBox
- Interactive certificates
- Efficient algorithms
- Determinant, rank, system solving, minimal and characteristic polynomials, normal forms.
- Methods of Danilevski, FFLAS, Dixon, Wiedemann, Villard, Krylov, etc.
|
|
PART 1: Arithmetics and complexity
-
Course 2 (November 30th, 2015):
Arithmetics
- Building finite fields
- Fast Euclidean Algorithm
- Primitive roots and irreducibility, ...
-
Course 3 (December 7th, 2015):
computations in Z, Q, K(X) (
Slides
)
- Chinese remaindering
- Rational Reconstruction
- CRT Codes and fault tolerance
-
Course 4 (December 7th, 2015):
Modelling: analysis of DNA sequences (
Slides
)
- String matching
- Pattern discovery
-
Course 5 (December 14th, 2015):
Fast integer and polynomial arithmetics in arbitrary precision
- divide and conquer for multiplication
- Karatsuba, Toom-Cook
- FFT
PART 2: Linear algebra in a field
-
Course 6 (December 14th, 2015):
Fast matrix multiplication algorithms
- Strassen-Winograd
- Space complexity
-
FFLAS
- Kronecker substitution, redQ
- M4RI
-
Course 7 (January 4th, 2016):
Gaussian elimination and reductions to matrix multiplicatin
-
TRSM and block recursive factorization
PLE/CUP
- Applications: inverse, determinant, system solving
-
Course 8 (January 4th, 2016):
Minimal and characteristic polynomials
- Krylov spaces and LU-Krylov method
- Keller-Gehrig algorithms
- Arithmetic progression
PART 3: Sparse and Blackbox linear algebra
-
Course 9 (January 11th, 2016):
Sparse methods and structure preserving methods
- Sparse Elimination
- Fill-in
- blackbox complexity model
- Berlekamp-Massey and Wiedemann algorithm
- Preconditioning and application to the computation
of the rank, the determinant, ...
PART 4: Arbitrary precision linear algebra (Z or K[X])
-
Course 10 (January 11th, 2016):
Computation in Z and binary complexity
- Evaluation/Interpolation and CRT
- Newton-like iterations: Dixon's and high-order liftings
-
Course 11 (January 18th, 2016):
smith normal form and algebraic topology (pattern
recognition, molecular interactions)
-
Course 12 (January 18th, 2016):
Interactive certificates
- Outsourcing and verified computations (linear time!)
- Complexity reductions (characteristic polynomial,
sparse matrices)
Talks (Monday February 1st, 2016)
The evaluation is by a bibliographic study with a report and an oral
presentation (about 15 minutes + questions).
The goal is to study in details a research paper (and potentially a
complementary paper). The choice of research paper is free but
should be related to the course. Some examples follow:
- Time-Optimal Interactive Proofs for Circuit Evaluation (pdf).
Justin Thaler, CRYPTO 2013.
Complementary paper:
Essentially optimal interactive certificates in linear algebra
(pdf).
Jean-Guillaume Dumas et Erich Kaltofen.
ISSAC 2014 : ACM International Symposium on Symbolic and Algebraic Computations, pages 146--153, Kobe, Japan, 23--25 Juillet 2014.
- Publicly Verifiable Delegation of Large Polynomials and
Matrix Computations, with Applications (pdf).
D. Fiore and R. Gennaro.
19th ACM Conference on Computer and Communications Security ACM CCS 2012, Raleigh, NC, USA. October 16-18, 2012. pp. 501-512.
Complementary paper:
Efficient Secure and Verifiable Outsourcing
of Matrix Multiplications
(pdf).
Y. Zhang and M. Blanton, , Information Security Conference (ISC'14),
Oct. 2014.
- Fast matrix rank algorithms and applications (pdf).
Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau.
Journal of the ACM, 60(5), #31, 2013
Complementary paper:
Efficient matrix preconditioners for black box linear algebra.
(pdf
). L. Chen, W. Eberly, E. Kaltofen, B. D. Saunders, W. J. Turner, and G. Villard. Linear Algebra and Applications, 343-344:119-146, 2002.
- Linear independence oracles and applications to rectangular and
low rank linear systems
(pdf).
Arne Storjohann and Shiyun Yang.
ISSAC, Kobe, Japan, juillet 2014.
Complementary paper :
A relaxed algorithm for online matrix inversion
(
pdf
). Arne Storjohann and Shiyun Yang. ISSAC, Bath, UK, 2015.
- On exact and approximate interpolation of sparse rational functions (pdf).
Erich Kaltofen and Zhengfeng Yang.
In ISSAC 2007 Proc. 2007 Internat. Symp. Symbolic Algebraic Comput. pages 203-210.
Complementary paper :
Early termination in sparse interpolation algorithms. (pdf)
Erich Kaltofen and Wen-shin Lee.
J. Symbolic Comput., 36(3-4):365-400, 2003.
- The bilinear complexity and practical algorithms for matrix
multiplication
(pdf)
A. V. Smirnov.
Computational Mathematics and Mathematical Physics
December 2013, Volume 53, Issue 12, pp 1781-1795.
Complementary paper :
Powers of Tensors and Fast Matrix Multiplication.
(pdf).
François Le Gall.
39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), pp. 296-303, 2014.
- Fast computation for Smith forms of sparse matrices over local rings.
(pdf)
Mustafa ElSheik, Mark Giesbrecht, Andrew Novocin, and
B. D. Saunders.
Proc. 2012 Internat. Symp. Symbolic Algebraic Comput.
ISSAC'12, Grenoble, France, July 22-25, pages 146-153, ACM Press, 2012.
Complementary paper :
Large matrix, small rank (pdf).
B. D. Saunders and B. Youse.
In Proc. International
Symposium on Symbolic and Algebraic Computation (ISSAC'09), pages 317--324, 2009.
Some course supports
Related books
-
[ACT]: Algebraic complexity theory
, Burgisser, Clausen, Shohrollahi
-
[MCA]: Modern Computer Algebra
, von zur Gathen and Gerhard
-
[MT]: Matrix Theory, vol. 1
, Gantmacher
-
[Cormen]: Introduction to Algorithms
, Cormen, Leiserson, Rivest
-
[DACA]: The Design and Analysis of Computer Algorithms
, Aho, Hopcroft, Ullman
Papers
Most of these can be found on line. Use for instance
google scholar
to find them. Ask me if a library account is needed.
-
An LLL-reduction algorithm with quasi-linear time complexity
(
pdf
).
-
[Albrecht & al 08]: Algorithm 898: Efficient Multiplication of Dense Matrices over GF(2)
(
pdf
).
-
[Baur Strassen 83]: The complexity of partial derivatives
Baur, Strassen, Theoretical Computer Science 22:317-330, 1983
-
[Berstein 09]: Optimizing linear maps modulo 2
(
pdf
).
-
[Bostan & al 08]: Solving structured linear systems with large displacement rank
(
pdf
)
-
[Bunch Hopcroft 74]: Triangular Factorization and Inversion by Fast Matrix Multiplication
Bunch, Hopcroft,
-
[Chen & Al 01]: Efficient matrix preconditioners for blackbox linear algebra
(
pdf
)
Chen, Eberly, Kaltofen, Saunders, Turner and Villard. Linear Algebra and its Applications, 343-344:119-146, 2002.
-
[Coppersmith & Winograd 90]: Matrix multiplication via arithmetic progessions,
Coppersmith, Winograd, J of Symbolic Computations, 9(3):251-280, 1990.
-
[Dixon 82] Exact solution of linear equations using p-adic expansions.
(
pdf
)
Dixon. Numer. Math. vol 40:137:141 (1982).
-
[Dumas & al 05]: Efficient computation of the characteristic polynomial
(
pdf
))
Dumas, Pernet, Wan, In proceedings of ISSAC'2005
-
[Dumas & al. 10]: Subspaces of matrices with special rank properties
(
pdf
)
Dumas, Gow, McGuire, Sheekey. Linear Algebra and its Applications 433(1):191-202, 2010.
-
[Jeannerod, Mouilleron 10]: Computing specified generators of structured matrix inverses,
(
pdf
)
-
[Keller-Gehrig 85]: Fast algorithms for the characteristic polynomial
Keller-Gehrig, In Theoretical Computer Science vol 36:309-317, 1985.
-
[Morgenstern]: How to compute fast a function and all its derivatives
(
pdf
)
Morgenstern, ACM SIGACT News, 16(4):60-62, 1985
-
[Nuel, Dumas 10]: Sparse approaches for the exact distribution of patterns in long multi-states sequences generated by a Markov source
(
pdf
)
Nuel, Dumas. Rapport de Recherche IMAG-hal-00492738, arXiv: math.Pr/1006.3246. 2010.
- [Parno & al. 13]: Pinocchio: Nearly Practical Verifiable
Computation (pdf)
Parno, Gentry, Howell, Raykova. IEEE Symposium on Security and Privacy, 21 May 2013.
-
[Pernet, Storjohann 07]: Faster algorithm for the characteristic polynomial
(
pdf
)
Pernet, Storjohann, In proceedings of ISSAC'2007
-
[Ruà & al. 09]: Classification of semifields of order 64
Rúa, Combarro, Ranilla. Journal of Algebra 322(11):4011-4029, 2009
-
[Storjohann 03] High order lifting and integrality certification.
(
pdf
)
Storjohann. Journal of Symbolic Computation, vol 36(3-4):613-648 (2003).
-
[Storjohann 96]: Faster Algorithms for Integer Lattice Basis Reduction.
(
pdf
).
-
[Strassen 69]: Gaussian elimination is not optimal,
Strassen, Numerische Mathematik, 13:354-356, 1969.
-
[Villard 00] Computing the Frobenius normal form of a sparse matrix
(
ps
)
Villard. In proceedings of CASC'00.
-
[Winograd 68]: A new algorithm for the inner product,
Winograd, IEEE transaction on computers, C-17(7):693-694, 1968.