skip to content
 

Validated computation tool for Perron-Frobenius eigenvalue using graph theory

Presented by: 
K Nagatou [Kyushu]
Date: 
Tuesday 13th March 2007 - 16:00 to 17:00
Venue: 
INI Seminar Room 1
Abstract: 

Any nonnegative matrix has a special eigenvalue, so called Perron-Frobenius eigenvalue, which plays an important role in dynamical systems. In this talk we present a numerical tool to compute rigorous (upper and lower) bounds of Perron-Frobenius eigenvalue of nonnegative matrices. Since a non-negative matrix corresponds to a directed graph, we make use of Tarjan's algorithm which founds all strongly connected components of a directed graph very efficiently. By applying Tarjan's algorithm to the directed graph which is derived from the original matrix, we decompose the matrix into (possibly small) irreducible components, and then enclose the aimed Perron-Frobenius eigenvalue. We show some numerical examples which demonstrate the efficiency of our tool.

University of Cambridge Research Councils UK
    Clay Mathematics Institute The Leverhulme Trust London Mathematical Society Microsoft Research NM Rothschild and Sons