Efficient Computation of a Canonical Form for a Generalized P-matrix

2012/04/27 by Walter D. Morris, Morris, Walter D. · 1 citation
Mathematics · Engineering · #Advanced Combinatorial Mathematics #graph theory and CDMA systems #Random Matrices and Applications

paper · pdf · doi:10.48550/arxiv.1204.6345

Abstract

We use recent results on algorithms for Markov decision problems to show that a canonical form for a generalized P-matrix can be computed, in some important cases, by a strongly polynomial algorithm.

Cited by

• A Strongly Polynomial Reduction for Linear Programs over Grids

Related

• A Canonical Form for Positive Definite Matrices
• Canonical forms for matrix tuples in polynomial time
• Matrix Canonical Forms
• A Polynomial-time Algorithm to Compute Generalized Hermite Normal Form of Matrices over Z[x]
• A Generalized Fundamental Matrix for Computing Fundamental Quantities of Markov Systems