Article

Creating Sparse Matrices

Create sparse matrices for factorization and solving systems.

Overview

In the Accelerate framework, Sparse Solvers stores sparse matrices using Compressed Sparse Column (CSC) format. CSC stores a matrix as a series of column vectors where the nonzero entries are specified as (row-index, value) pairs and the zero entries are omitted.

Routines are provided to convert matrices from other formats to CSC. For more information, see Conversion from Other Formats.

The Accelerate framework supports unsymmetric and symmetric sparse matrices, each of which can also be blocked.

  • An unsymmetric matrix contains either Double or Float values with no symmetry between its lower-left and upper-right triangles.

  • A symmetric matrix is symmetrical along the diagonal from its upper-left to lower-right corners. In other words, a symmetric matrix is equal to its transpose (A=Aᵀ).

  • A block matrix can be either unsymmetric or symmetric and is broken into sections called blocks. The blocks along the diagonal of a symmetrical block matrix must, themselves, be symmetrical.

Create an Unsymmetric Matrix

In this example of an unsymmetric sparse matrix, empty cells represent zeros:

Example of an unsymmetric sparse matrix, empty cells represent zeros.

The first step in creating a matrix is to create two arrays that store the row indices and corresponding values:

var rowIndices: [Int32] = [0, 1, 3,     // Column 0
                           0, 1, 2, 3,  // Column 1
                           1, 2]        // Column 2
 
var values = [2.0, -0.2, 2.5,           // Column 0
              1.0, 3.2, -0.1, 1.1,      // Column 1
              1.4, 0.5]                 // Column 2

In addition to the (row-index, value) pairs, you need to create a third array that specifies where each column starts. This array requires an additional, final entry that defines the final column's length.

In the following example, the zeroth item in the values array starts column 0, the third starts column 1, and the seventh starts column 2:

var columnStarts = [0,    // Column 0
                    3,    // Column 1
                    7,    // Column 2
                    9]

The two structural arrays, rowIndices and columnStarts, are used to create a SparseMatrixStructure instance that describes the matrix's structure. The initializer requires an attributes object, and the default parameters of a SparseAttributes_t instance specify an unsymmetric matrix:

let structure = SparseMatrixStructure(rowCount: 4,
                                      columnCount: 3,
                                      columnStarts: &columnStarts,
                                      rowIndices: &rowIndices,
                                      attributes: SparseAttributes_t(),
                                      blockSize: 1)

With the structure and values defined, you can create a SparseMatrix_Double instance:

let A = SparseMatrix_Double(structure: structure,
                            data: &values)

Create a Symmetric Matrix

In this example of a symmetric sparse matrix, empty cells represent zeros:

Example of a symmetric sparse matrix, empty cells represent zeros.

Because it is symmetric, the values in the upper triangle of the matrix are redundant and should be excluded from the data passed to the SparseMatrix_Double initializer. This example shows the excluded values in gray:

Example of a symmetric sparse matrix, excluded values in gray.

As with the unsymmetric example, the rowIndices array specifies the row in the matrix that contains the corresponding item in values, and the columnStarts array specifies where each column starts in the rowIndices array.

In this case, the attributes parameter allows you to specify that the matrix is symmetric and the items in the values array are derived from the lower triangle:

var columnStarts = [0,                  // Column 0    
                    3,                  // Column 1      
                    6,                  // Column 2
                    7,                  // Column 3
                    8]
 
var rowIndices: [Int32] = [0, 1, 3,     // Column 0
                           1, 2, 3,     // Column 1
                           2,           // Column 2
                           3]           // Column 3
  
var attributes = SparseAttributes_t()
attributes.triangle = SparseLowerTriangle
attributes.kind = SparseSymmetric
 
let structure = SparseMatrixStructure(rowCount: 4,
                                      columnCount: 4,
                                      columnStarts: &columnStarts,
                                      rowIndices: &rowIndices,
                                      attributes: attributes,
                                      blockSize: 1)

The SparseMatrix_Double instance is created using the structure created above and the values from the lower triangle of the matrix:

var values = [10.0,  1.0, 2.5,  // Column 0
              12.0, -0.3, 1.1,  // Column 1
              9.5,              // Column 2
              6.0]              // Column 3
  
let A = SparseMatrix_Double(structure: structure,
                            data: &values)

Create a Block Matrix

You can create sparse matrices that are blocked—separated into blocks that contain multiple values—defining a blockSize greater than 1. The block size is the length of the side of the square block.

Block matrices can be symmetric or unsymmetric. This example shows an unsymmetric sparse matrix with a block size of 3:

Example of an unsymmetric sparse matrix with a block size of 3.

The following example shows the code required to create a sparse matrix with the structure and values shown above. The block size of 3 is specified in the SparseMatrixStructure. The values for each block are concatenated in column-major order.

var columnStarts = [ 0, 2, 4, 5 ]
var rowIndices: [Int32] = [ 0, 2, 0, 1, 2 ]
 
var values = [
    1.0, 0.1, 9.2, 0.3, 0.5, 1.3, 0.2, 1.3, 4.5,    // Block 0
    0.2, 0.7, 0.9, 1.8, 1.6, 1.7, 0.8, 0.7, 0.9,    // Block 1
    1.5, 2.5, 7.2, 0.2, 0.8, 0.8, 0.3, 0.4, 0.2,    // Block 2
    0.2, 0.4, 1.8, 1.6, 1.8, 0.6, 0.5, 4.2, 3.3,    // Block 3
    0.2, 0.8, 1.2, 0.4, 0.6, 0.8, 1.8, 1.2, 0.9     // Block 4
]  
var attributes = SparseAttributes_t()
attributes.kind = SparseOrdinary
 
let structure = SparseMatrixStructure(rowCount: 3,
                                      columnCount: 3,
                                      columnStarts: &columnStarts,
                                      rowIndices: &rowIndices,
                                      attributes: attributes,
                                      blockSize: 3)
 
let A = SparseMatrix_Double(structure: structure,
                            data: &values)

When creating a symmetric matrix with a block size greater than 1, the blocks along the matrix's diagonal must also be symmetric.

See Also

Sparse Matrices

struct SparseMatrix_Double

A structure that contains a sparse matrix of double-precision, floating-point values.

struct SparseMatrix_Float

A structure that contains a sparse matrix of single-precision, floating-point values.

Conversion from Other Formats

Create sparse matrices from coordinate format arrays and BLAS opaque matrices.