Iterative methods for Non-Hermitian Problems and Related Matrix Analysis

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Edelman 0209437 The investigator, Marko Huhtanen, studies iterative methods and develops related matrix analysis for solving large-scale problems in linear algebra. The emphasis is on problems involving non-Hermitian matrices. Recently he has extended optimal methods for Hermitian matrices to problems with normal matrices. This gave rise to two fundamentally different families of algorithms. One is based on a direct extension of the classical Hermitian Lanczos algorithm and the other on using real analytic techniques. These methods can be employed, e.g., in solving linear systems and finding eigenvalues, as well as in multivariate least squares approximation problems and interpolation. Moreover, he has introduced a classification of normal matrices to measure complexity of the algorithms. In light of these methods the investigator aims at finding ways to extend these solution techniques to nonnormal problems. The matrix analytic part of the study deals with, e.g., matrix nearness problems and classes of matrices with which matrix-vector products can be performed inexpensively, typically with the FFT techniques. The motivation behind the project is to increase the speed of computations for solving real world problems. Modeling problems of science and engineering realistically leads invariably to large scale problems. Then the number of unknowns to be solved can be millions. To solve problems of this size within a reasonable time limit calls for new algorithms and solution techniques. A concrete example can be given with signal processing: a faster algorithm means faster signal processing and the fast Fourier transformation has revolutionized this particular field of engineering. The investigator studies methods at the most fundamental level of numerical analysis because linear systems need to be solved practically in every problem one can imagine. Consequently, the impact of the study can be very large. In addition to inventing fast solution methods, in this project mathematical tools are developed that are of interest from a pure matrix analytic point of view.