matrix *-algebra

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

    Efficient high-precision dense matrix algebra on parallel architectures for nonlinear discrete optimization

  • John Gunnels
  • Jon Lee
  • Susan Margulies
    • Categories Combinatorial Optimization, Graphs and Matroids, Parallel Algorithms Tags , , , , , , , , , ,

    We provide a proof point for the idea that matrix-based algorithms for discrete optimization problems, mainly conceived for proving theoretical efficiency, can be easily and efficiently implemented on massively-parallel architectures by exploiting scalable and efficient parallel implementations of algorithms for ultra high-precision dense linear algebra. We have successfully implemented our algorithm on the Blue Gene/L … Read more

    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