Nonnegative Matrix Factorization: Algorithms, Complexity and Applications

Slides

Abstract: How quickly can we compute the nonnegative rank (r) of an m × n matrix? Indeed, this problem --- and the companion problem of finding a nonnegative matrix factorization with minimum inner-dimension --- has a rich history, with applications in quantum mechanics, probability theory, data analysis, communication complexity and polyhedral combinatorics. Here we will survey the recent progress on this question, that has essentially resolved its worst-case complexity.

It was known that it is NP-hard to compute the nonnegative rank, and that it can be computed in time exponential in n, m and r by appealing to the existential theory of the reals. Here we will give improved algorithms that run in time (nm)^(O(r^2)), and thus run in polynomial time for any constant r. Indeed, prior to our work the best known algorithm even for the case r = 4 ran in exponential time. We will complement this with an intractability result that shows any algorithm that runs in time (nm)^(O(r)) would violate the exponential time hypothesis. Moreover, we will emphasize an algebraic perspective where a reformulation of nonnegative rank as a system of polynomial inequalities with surprisingly few variables is what leads to nearly optimal algorithms for this problem.

We will also discuss some of the applications of nonnegative rank, and open questions where algebraic perspectives could lead to new lower bounds in polyhedral combinatorics.

Exact Linear Algebra Algorithmic: Theory and Practice

Slides

Abstract: Exact linear algebra is a core component of many symbolic and algebraic computations, as it often delivers competitive theoretical complexities and also better harnesses the efficiency of modern computing infrastructures. In this tutorial we will present an overview on the recent advances in exact linear algebra algorithmic and implementation techniques, and highlight the few key ideas that have proven successful in their design. As an illustration, we will study in more details the computation of some matrix normal forms over a finite field or the ring of polynomials, specific to computer algebra. In particular, we will give a special care to the design and implementation of parallel exact linear algebra routines, trying to emphasize the similarities and distinctness with parallel numerical linear algebra. We aim to provide the working computer algebraist with a set of best practices for the use or the design of exact linear algebra software, together with an overview on a few still unresolved algorithmic problems in the field.

An Introduction to Finite Element Methods

Slides

Abstract: One of the most common techniques for obtaining numerical solutions to partial differential equations on non-trivial domains are (high order) finite element methods. The given domain is subdivided in simple geometric objects and an approximate solution is computed as a linear combination of locally supported basis functions. In the past decade there have been several successful collaborations between mathematicians from numerical analysis and computer algebra to analyze or improve the numerical methods. The applied methods include Groebner bases, Cylindrical Algebraic Decomposition, algorithms for special functions, etc. In this tutorial we plan to present an introduction to the basic concepts of finite element methods and we want to close with an overview on some of those recent collaborations and the involved proof techniques.