Optimization Online


A Numerical Algorithm for Block-Diagonal Decomposition of Matrix *-Algebras, Part I: Proposed Approach and Application to Semidefinite Programming

Kazuo Murota (murota***at***mist.i.u-tokyo.ac.jp)
Yoshihiro Kanno (kanno***at***mist.i.u-tokyo.ac.jp)
Masakazu Kojima (kojima***at***is.titech.ac.jp)
Sadayoshi Kojima (sadayosi***at***is.titech.ac.jp)

Abstract: Motivated by recent interest in group-symmetry in semidefinite programming, we propose a numerical method for finding a finest simultaneous block-diagonalization of a finite number of matrices, or equivalently the irreducible decomposition of the generated matrix *-algebra. The method is composed of numerical-linear algebraic computations such as eigenvalue computation, and automatically makes 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. The main issues of the proposed approach are presented in this paper under some assumptions, while the companion paper (Part II) gives an algorithm with full generality. Numerical examples of truss and frame designs 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 (revised in October 2008 / revised in May 2009).

Download: [PDF]

Entry Submitted: 10/14/2007
Entry Accepted: 10/15/2007
Entry Last Modified: 05/11/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society