Algorithms for determining the copositivity of a given symmetric matrix (Q959864): Difference between revisions

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.