A Numerical Algorithm for Block-Diagonal Decomposition of Matrix *-Algebras, Part II: General Algorithm

An algorithm is proposed for finding the finest simultaneous block-diagonalization of a finite number of square matrices, or equivalently the irreducible decomposition of a matrix *-algebra given in terms of its generators. This extends the approach initiated in Part I by Murota-Kanno-Kojima-Kojima. The algorithm, composed of numerical-linear algebraic computations, does not require any algebraic structure … Read more

Lecture notes: Semidefinite programs and harmonic analysis

Lecture notes for the tutorial at the workshop HPOPT 2008 – 10th International Workshop on High Performance Optimization Techniques (Algebraic Structure in Semidefinite Programming), June 11th to 13th, 2008, Tilburg University, The Netherlands. Citation arXiv:0809.2017v1 [math.OC] Article Download View Lecture notes: Semidefinite programs and harmonic analysis

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

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 … Read more

Symmetry in semidefinite programs

This paper is a tutorial in a general and explicit procedure to simplify semidefinite programming problems which are invariant under the action of a group. The procedure is based on basic notions of representation theory of finite groups. As an example we derive the block diagonalization of the Terwilliger algebra in this framework. Here its … Read more

Approximating the Chromatic Number of a Graph by Semidefinite Programming

We investigate hierarchies of semidefinite approximations for the chromatic number $\chi(G)$ of a graph $G$. We introduce an operator $\Psi$ mapping any graph parameter $\beta(G)$, nested between the stability number $\alpha(G)$ and $\chi(\bar G)$, to a new graph parameter $\Psi_\beta(G)$, nested between $\omega(G)$ and $\chi(G)$; $\Psi_\beta(G)$ is polynomial time computable if $\beta(G)$ is. As an … Read more