Dr. Anil Hirani, Applied Mathematician
Dept. of Computer Science - University of Illinois at Urbana-Champaign
Applied topology is a relatively new field. This talk is a survey of matrix based methods which extend its reach in new directions. (1) Given a sparse set of pairwise comparisons (between objects, sports teams, movies, candidates, etc.) a global ranking can be computed as a least squares problem. Digging deeper, newer applications of such data become possible with Hodge decomposition. I will show how to do this efficiently on many types of graphs using various matrix methods. One application will be to rank NCAA Men's Basketball teams. One surprise is the failure of a technique which is otherwise quite popular in traditional scientific computing. (2) Harmonic forms are one piece of Hodge decomposition. These have been widely used in computer graphics for texture mapping and vector field design. I will show their use in locating holes in idealized sensor networks by solving certain linear systems. Then I'll show how to use eigenvector and least squares methods to find harmonic forms on meshes. These can then be used to solve vector elliptic partial differential equations in topologically interesting domains. (3) The above problems are both related to L2 (2-norm) minimization. In contrast L1 (1-norm) minimization has sometimes been hailed as the technique to supplant least squares for this century's problems. I will show how the use of 1-norm transforms two NP-hard topological problems into polynomial time solvable problems.