BIMSA >
BIMSA Topology Seminar
Homological obstructions to existence of diagonalization algorithms for sparse matrices
Homological obstructions to existence of diagonalization algorithms for sparse matrices
演讲者
Anton Ayzenberg
时间
2024年05月16日 14:30 至 15:30
地点
A3-4-101
线上
Zoom 928 682 9093
(BIMSA)
摘要
For a simple graph Γ on n vertices, consider a space M(Γ, λ) of all Γ-shaped Hermitian matrices of size n with a given simple spectrum λ. Here a graph is used to encode a sparsity type of a matrix. For a generic spectrum, the manifold M(Γ, λ) is smooth and carries a canonical torus action with isolated fixed points, making it a subject of interest in toric topology.
We proved an alternative:
(1) Γ is a proper interval graph. Matrices have Hessenberg shape. The manifold M(Γ, λ) of such matrices is cohomologically equivariantly formal. The total Betti number β(M(Γ,λ)) equals n!. There exist asymptotical diagonalization algorithms for such matrices (e.g. QR-algorithm and Toda flow).
(2) Γ is not proper interval. M(Γ, λ) is not equivariantly formal. We have β(M(Γ, λ))>n!. No asymptotical diagonalization algorithm of Morse-Smale type exists for such sparsity shapes.
The same alternative is valid for real symmetric matrices.
The proof required two principal steps, theoretical and computational. We proved a general result in toric topology relating equivariant formality of manifolds with torus actions with acyclicity of their underlying combinatorial structures, face posets. We then computed, on our Lab's cluster, homology of face posets of specific isospectral matrix manifolds and GKM-sheaves - to prove that these manifolds are not equivariantly formal without computing their own cohomology directly.
This talk is based on my works with V. Buchstaber, V. Cherepanov, M. Masuda, G. Solomadin, and K. Sorokin.
We proved an alternative:
(1) Γ is a proper interval graph. Matrices have Hessenberg shape. The manifold M(Γ, λ) of such matrices is cohomologically equivariantly formal. The total Betti number β(M(Γ,λ)) equals n!. There exist asymptotical diagonalization algorithms for such matrices (e.g. QR-algorithm and Toda flow).
(2) Γ is not proper interval. M(Γ, λ) is not equivariantly formal. We have β(M(Γ, λ))>n!. No asymptotical diagonalization algorithm of Morse-Smale type exists for such sparsity shapes.
The same alternative is valid for real symmetric matrices.
The proof required two principal steps, theoretical and computational. We proved a general result in toric topology relating equivariant formality of manifolds with torus actions with acyclicity of their underlying combinatorial structures, face posets. We then computed, on our Lab's cluster, homology of face posets of specific isospectral matrix manifolds and GKM-sheaves - to prove that these manifolds are not equivariantly formal without computing their own cohomology directly.
This talk is based on my works with V. Buchstaber, V. Cherepanov, M. Masuda, G. Solomadin, and K. Sorokin.