Document Actions

6.1 Creating Sparse Matrices

6.1 Creating Sparse Matrices A general spmatrix object can be thought of as a triplet description of a sparse matrix, i.e., a list of entries of the matrix, with for each entry the value, row index, and column index. Entries that are not included in the list are assumed to be zero. For example, the sparse matrix

$\begin{displaymath} A = \left[ \begin{array}{rrrrr} 0 & 2 & 0 & 0 & 3 \\ 2 &... ...-1 & -2 & 0 & 4 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{array} \right] \end{displaymath}$

(6.1)

has the triplet description

$\begin{displaymath} (2,1,0), \qquad (-1,2,0), \qquad (2,0,1), \qquad (-2,2,1), \qquad (1,3,2), \qquad (4,2,3), \qquad (3,0,4). \end{displaymath}$

The list may include entries with a zero value, so triplet descriptions are not necessarily unique. The list

$\begin{displaymath} (2,1,0), \qquad (-1,2,0), \qquad (0,3,0), \qquad (2,0,1), \qquad (-2,2,1), \qquad (1,3,2), \qquad (4,2,3), \qquad (3,0,4) \end{displaymath}$

is another triplet description of the same matrix.

An spmatrix object corresponds to a particular triplet description of a sparse matrix. We will refer to the entries in the triplet description as the nonzero entries of the object, even though they may have a numerical value zero.

Two functions are provided to create sparse matrices. The first, spmatrix(), constructs a sparse matrix from a triplet description.

spmatrix(x, I, J[, size[, tc]])

I and J are sequences of integers (lists, tuples, array arrays, xrange objects, ...) or integer matrices (matrix objects with typecode 'i'), containing the row and column indices of the nonzero entries. The lengths of I and J must be equal. If they are matrices, they are treated as lists of indices stored in column-major order, i.e., as lists list(I), respectively, list(J).

size is a tuple of nonnegative integers with the row and column dimensions of the matrix. The size argument is only needed when creating a matrix with a zero last row or last column. If size is not specified, it is determined from I and J: the default value for size[0] is max(I)+1 if I is nonempty and zero otherwise. The default value for size[1] is max(J)+1 if J is nonempty and zero otherwise.

tc is the typecode, 'd' or 'z', for double and complex matrices, respectively. Integer sparse matrices are not implemented.

x can be a number, a sequence of numbers, or a dense matrix. This argument specifies the numerical values of the nonzero entries.

If x is a number (Python integer, float or complex), a matrix is created with the sparsity pattern defined by I and J, and nonzero entries initialized to the value of x. The default value of tc is 'd' if x is integer or float, and 'z' if x is complex.
The following code creates a 4 by 4 sparse identity matrix.
```
>>> from cvxopt.base import spmatrix
>>> A = spmatrix(1.0, range(4), range(4))
>>> print A  
[ 1.00e+00     0         0         0    ]
[    0      1.00e+00     0         0    ]
[    0         0      1.00e+00     0    ]
[    0         0         0      1.00e+00]
```
If x is a sequence of numbers, a sparse matrix is created with the entries of x copied to the entries indexed by I and J. The list x must have the same length as I and J. The default value of tc is determined from the elements of x: 'd' if x contains integers and floating-point numbers or if x is an empty list, and 'z' if x contains at least one complex number.
As an example, the matrix (6.1) can be created as follows.
```
>>> A = spmatrix([2,-1,2,-2,1,4,3], [1,2,0,2,3,2,0], [0,0,1,1,2,3,4])
>>> print A 
[    0      2.00e+00     0         0      3.00e+00]
[ 2.00e+00     0         0         0         0    ]
[-1.00e+00 -2.00e+00     0      4.00e+00     0    ]
[    0         0      1.00e+00     0         0    ]
```
If x is a dense matrix, a sparse matrix is created with all the entries of x copied, in column-major order, to the entries indexed by I and J. The matrix x must have the same length as I and J. The default value of tc is 'd' if x is an 'i' or 'd' matrix, and 'z' otherwise.

If I and J contain repeated entries, the corresponding values of the coefficients are added.

The function sparse() constructs a sparse matrix from a block-matrix description.

sparse(x[, tc])

tc is the typecode, 'd' or 'z', for double and complex matrices, respectively.

x can be a matrix, spmatrix, or a list of lists of matrices (matrix or spmatrix objects) and numbers (Python integer, float or complex).

If x is a matrix or spmatrix object, then a sparse matrix of the same size and the same numerical value is created. Numerical zeros in x are treated as structural zeros and removed from the triplet description of the new sparse matrix.

If x is a list of lists of matrices (matrix or spmatrix) and numbers (Python integer, float or complex) then each element of x is interpreted as a (block-)column matrix stored in colum-major order, and a block-matrix is constructed by juxtaposing the len(x) block-columns (as in matrix(), see section 2.1). Numerical zeros are removed from the triplet description of the new matrix.

The following example shows how to construct a sparse block-matrix.

>>> from cvxopt.base import matrix, spmatrix, sparse
>>> A = matrix([[1, 2, 0], [2, 1, 2], [0, 2, 1]])
>>> B = spmatrix([], [], [], (3,3))
>>> C = spmatrix([3, 4, 5], [0, 1, 2], [0, 1, 2])
>>> D = sparse([[A, B], [B, C]])
>>> print D
[ 1.00e+00  2.00e+00     0         0         0         0    ]
[ 2.00e+00  1.00e+00  2.00e+00     0         0         0    ]
[    0      2.00e+00  1.00e+00     0         0         0    ]
[    0         0         0      3.00e+00     0         0    ]
[    0         0         0         0      4.00e+00     0    ]
[    0         0         0         0         0      5.00e+00]

A matrix with a single block-column can be represented by a single list.

>>> D = sparse([A, C])
>>> print D
[ 1.00e+00  2.00e+00     0    ]
[ 2.00e+00  1.00e+00  2.00e+00]
[    0      2.00e+00  1.00e+00]
[ 3.00e+00     0         0    ]
[    0      4.00e+00     0    ]
[    0         0      5.00e+00]

The function spdiag() constructs a block-diagonal sparse matrix from a list of matrices.

spdiag(x)

x is a matrix with a single row or column, or a list of square dense or sparse matrices or scalars. If x is matrix, a sparse diagonal matrix is returned with the entries of x on its diagonal. If x is list, a sparse block-diagonal matrix is returned with the element in the list as its diagonal blocks.

The following example shows how to construct a sparse block-diagonal matrix.

>>> from cvxopt.base import matrix, spmatrix, spdiag
>>> A = 3.0
>>> B = matrix([[1,-2],[-2,1]])
>>> C = spmatrix([1,1,1,1,1],[0,1,2,0,0,],[0,0,0,1,2])
>>> D = spdiag([A, B, C])
>>> print D
[ 3.00e+00     0         0         0         0         0    ]
[    0      1.00e+00 -2.00e+00     0         0         0    ]
[    0     -2.00e+00  1.00e+00     0         0         0    ]
[    0         0         0      1.00e+00  1.00e+00  1.00e+00]
[    0         0         0      1.00e+00     0         0    ]
[    0         0         0      1.00e+00     0         0    ]

CVXOPT

Sections

Personal tools

Document Actions

6.1 Creating Sparse Matrices