A Numerical Algorithm for Block-Diagonal Decomposition of Matrix *-Algebras

Kazuo Murota (murotamist.i.u-tokyo.ac.jp)
Yoshihiro Kanno (kannomist.i.u-tokyo.ac.jp)
Masakazu Kojima (kojimais.titech.ac.jp)
Sadayoshi Kojima (sadayosiis.titech.ac.jp)

Abstract: Motivated by recent interest in group-symmetry in the area of semidefinite programming, we propose a numerical method for finding a finest simultaneous block-diagonalization of a finite number of symmetric matrices, or equivalently the irreducible decomposition of the matrix *-algebra generated by symmetric matrices. The method does not require any algebraic structure to be known in advance, whereas its validity relies on matrix *-algebra theory. The method is composed of numerical-linear algebraic computations such as eigenvalue computation, and automatically makes the full use of the underlying algebraic structure, which is often an outcome of physical or geometrical symmetry, sparsity, and structural or numerical degeneracy in the given matrices. Numerical examples of truss design are also presented.

Keywords: matrix *-algebra, block-diagonalization, group symmetry, sparsity, semidefinite programming

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Applications -- Science and Engineering

Citation: METR 2007-52, Department of Mathematical Informatics, University of Tokyo, Japan, September, 2007.

Download: [PDF]

Entry Submitted: 10/14/2007
Entry Accepted: 10/15/2007
Entry Last Modified: 10/15/2007

Modify/Update this entry