An efficient storage scheme for SQL

 

In the User's Guide for SDPpack Version 0.8 Beta[8], an ASCII storage format for SDP was suggested, based on one communicated to us by A. Nemirovskii. Here, we further extend this to represent SQL problems. We essentially have two cases: the matrices are (i) dense, or (ii) sparse, and in each case, the matrix is represented in a different way. In all cases below, we store one number per line in the file (so that the file may be read efficiently using Matlab's load command), although the text sometimes shows several entries on the same line for clarity.

Semidefinite part

We need to store the cost matrix as well as the constraint matrices , corresponding to the rows of the matrix . Suppose X is a block diagonal matrix with block structure . We respresent the ith diagonal block of this matrix by X(i), and the (j,k) element within the ith block as .

Case (i)

For the first block, we first record a 0 (denoting that the block is dense), and then the entries in the upper triangular part of the matrix are provided row-wise.

(Similar segments for the remaining blocks .)

Case (ii)

For the first block, we first record a 1 (denoting that the block is sparse), then the number of nonzero entries in the upper triangular part of the block, say n. Then, for , we record the row number , the column number , and the value of the corresponding nonzero entry .

(Similar segments for the remaining blocks .) The row and the column indices are into the block, and not into the whole matrix X.

Note: at present, the code does not permit mixing sparse and dense matrix blocks: the blocks must be either all dense or all sparse.

Quadratic part

Here, we need to store the constraint matrix , which has m rows and columns.

Case (i)

We first record a 0 if the constraint matrix is dense. Then, the elements of the constraint matrix are given column-wise.

Case (ii)

We first record a 1 if the constraint matrix is sparse, then the number of nonzero entries in the matrix. Then, for each nonzero entry, we record the row number, the column number and the value of the corresponding entry.

Linear part

Here, we need to store the constraint matrix of size .

Case (i)

We first record a 0 if the constraint matrix is dense. Then, the elements of the constraint matrix are given column-wise.

Case (ii)

We first record a 1 if the constraint matrix is sparse, then the number of nonzero entries in the matrix. Then, for each nonzero entry, we record the row number, the column number and the value of the corresponding entry.

In Table A, we describe the overall storage format for an SQLP; matrices for each of the three parts (semidefinite, quadratic and linear) are stored as just described. The C-style comments are not a part of the storage format.

  
Table 2: ASCII storage format for SQLP's