block diagonalization

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

  • Takanori Maehara
  • Kazuo Murota
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , , , ,

    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

  • Frank Vallentin
    • Categories Infinite Dimensional Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , , ,

    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. CitationarXiv:0809.2017v1 [math.OC]ArticleDownload View PDF

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

  • Yoshihiro Kanno
  • Masakazu Kojima
  • Kazuo Murota
  • Sadayoshi Kojima
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , , , ,

    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

  • Frank Vallentin
    • Categories Semi-definite Programming Tags , , ,

    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

  • N. Gvozdenovic
  • Monique Laurent
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    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