Given rational symmetric matrices A0, A1, .., An of size m, let S denote the set of real points x = (x1, .. ,xn) such that the matrix A(x) = A0 + A1 x1 + .. + An xn is positive semidefinite. The set S is a convex semialgebraic set called a spectrahedron, it is described by a Linear Matrix Inequality, an LMI. The above figure represents a specific spectrahedron S for n=3 and m=5. The boundary of S is in red. The determinant of A(x) vanishes on this red surface, but also on the blue surface.
SPECTRA is a Maple library which aims at finding at least one point in S, using exact arithmetic.
SPECTRA should be used when the number n of variables or the size m of the LMI are small. It should not be considered as a competitor to numerical algorithms such as interior-point methods for semidefinite programming (SDP).
Contrary to numerical algorithms which are based on approximate computations and floating point arithmetic, SPECTRA is exclusively based on computations with exact arithmetic, and hence it should be primarily used either in potentially degenerate situations, for example when it is expected that S has empty interior, or when a rigorous certificate of infeasibility or feasibility is required.
SPECTRA 1.0 (5 November 2016) is freely available as a Maple library. It can be downloaded in the form of a single binary file called SPECTRA.mla
SPECTRA relies on FGb, a library for fast computation of Groebner bases, whose Maple interface must be installed.
A light documentation of SPECTRA including simple examples is available here:
A more detailed documentation introducing the theoretical background and including more sophisticated examples is available here:
SPECTRA is based on the mathematical theory and the computer algebra algorithm described comprehensively in the following documents:
Please forward comments, suggestions and bug reports to Didier Henrion, Simone Naldi and Mohab Safey El Din.