Linear-Time Complete Positivity Detection and Decomposition of Sparse Matrices

DOI10.1137/110848177zbMath1268.65063OpenAlexW2018776261MaRDI QIDQ4902917

Peter J. C. Dickinson, Mirjam Dür

Publication date: 18 January 2013

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://pure.rug.nl/ws/files/2474102/2012SIAMJMatrixAnalApplDickinson.pdf

zbMATH Keywords

algorithmsparse matrixcomplete positivitylinear-timerank-one decomposition

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Factorization of matrices (15A23) Positive matrices and their generalizations; cones of matrices (15B48)

Related Items (15)

On the number of CP factorizations of a completely positive matrix ⋮ A polynomial-time algorithm for computing low CP-rank decompositions ⋮ An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix ⋮ Completely positive factorizations associated with Euclidean distance matrices corresponding to an arithmetic progression ⋮ A factorization method for completely positive matrices ⋮ Completely positive factorization by a Riemannian smoothing method ⋮ Interiors of completely positive cones ⋮ Factorization and cutting planes for completely positive matrices by copositive projection ⋮ On the computational complexity of membership problems for the completely positive cone and its dual ⋮ Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017 ⋮ The \(\mathcal A\)-truncated \(K\)-moment problem ⋮ Completely positive matrices: real, rational, and integral ⋮ Building a completely positive factorization ⋮ Lower bounds on matrix factorization ranks via noncommutative polynomial optimization ⋮ The complete positivity of symmetric tridiagonal and pentadiagonal matrices

This page was built for publication: Linear-Time Complete Positivity Detection and Decomposition of Sparse Matrices