Algorithms for determining the copositivity of a given symmetric matrix
type: Item
instance of: scholarly article
title: Algorithms for determining the copositivity of a given symmetric matrix
zbMATH Open document ID: 1161.65033
author: Shangjun Yang
author: Xiaoxin Li
published in: Linear Algebra and its Applications
publication date: 2008-12-12T00:00:00Z
review text: Copositive matrices are important in matrix theory and its applications. Many paper are dealing with quick algorithms of determining copositivity of a given symmetric matrix. The reason of the wide interest in this topic are applications in numerical methods concerning large linear system solution or related eigenvalue problems. The general problem of testing for co-positivity of a real symmetric matrix \(\mathbf A \in \mathbb R^{m\times n}\) represents an NP-complete problem defined by the same authors in previous papers. The authors conclude that a fully general algorithm for determining the copositivity of a matrix \(\mathbf A\) does not exist until now. Some sub-classes of matrices \(\mathbf A\) only can be treated as it follows from several references. The paper in question provides five new algorithms for matrices of order 3-7 giving quickly the complete answer for the test of copositivity with a following resolution: not copositive, copositive, strictly copositive. The sixth algorithm is developed for matrices of order \(n\geq 8\). Although it does not guarantee that a unique answer will be provided, a still acceptable result is mostly given. If it exceptionally fails, adequate information is reported. All steps are carefully substantiated. Deduction proceeds with caution in a form of theorems and corollaries (including proofs) utilizing results of earlier publications. Implementation of algorithms and their realization in a MATLAB form are described in details. Comprehensive numerical experiments are done together with transparent interpretation. Computational effectivity and reliability are evaluated. The list of references is large enough referencing many papers appeared in recent time related directly with the topic itself (including one self-reference) as well as some resources noticing historical backgrounds of the problem.
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 15A18
Mathematics Subject Classification ID: 65F15
Mathematics Subject Classification ID: 15B48
zbMATH DE Number: 5382403
zbMATH Keywords: strictly co-positive
zbMATH Keywords: \(Z\)-matrices
zbMATH Keywords: simplex
zbMATH Keywords: Perron root
zbMATH Keywords: co-positive matrices
zbMATH Keywords: algorithms
zbMATH Keywords: test of co-positivity
zbMATH Keywords: numerical experiments
zbMATH Keywords: computational effectivity
reviewed by: Jiri Náprstek
describes a project that uses: Matlab
MaRDI profile type: Publication
full work available at URL: j.laa.2008.07.028
OpenAlex ID: W2098483431
cites work: Criteria for copositive matrices using simplices and barycentric coordinates
cites work: On copositive matrices
cites work: Copositive matrices and Simpson's paradox
cites work: The copositive completion problem
cites work: Spectral theory of copositive matrices
cites work: A copositivity probe
cites work: A test for copositive matrices
cites work: Some NP-complete problems in quadratic and nonlinear programming
cites work: Criteria for copositive matrices
cites work: Quadratic-programming criteria for copositive matrices
DOI: 10.1016/J.LAA.2008.07.028
description: scientific article; zbMATH DE number 5382403