Reference

Empties the InsterableSparseVector in O(1) operations.

Make the head pointer do a self-loop.

Empty the SparseVectorAccumulator in O(1) operations.

For the L-factor: insert in row head column value For the U-factor: insert in column head row value

Insert index after a known value after

_fillblock_gpu

Fill the dense blocks of the preconditioner from the sparse CSR matrix arrays

Sets v[idx] += a when idx is occupied, or sets v[idx] = a. Complexity is O(nnz). The prev_idx can be used to start the linear search at prev_idx, useful when multiple already sorted values are added.

Add without providing a previous index.

Sets v[idx] += a when idx is occupied, or sets v[idx] = a. Complexity is O(1).

Basically A[:, j] = scale * drop(y), where drop removes values less than drop. Note: sorts the nzind's of y, so that the column can be appended to a SparseMatrixCSC.

Resets the SparseVectorAccumulator.

Note: does not update A.colptr for columns > j + 1, as that is done during the steps.

Basically A[:, j] = scale * drop(y), where drop removes values less than drop.

Resets the InsertableSparseVector.

Note: does not update A.colptr for columns > j + 1, as that is done during the steps.

Applies in-place backward substitution with the U factor of F, under the assumptions:

1. U is stored transposed / row-wise
2. U has no lower-triangular elements stored
3. U has (nonzero) diagonal elements stored.

build_adjmatrix

Build the adjacency matrix of a matrix A corresponding to the undirected graph

Applies in-place forward substitution with the L factor of F, under the assumptions:

1. L is stored column-wise (unlike U)
2. L has no upper triangular elements
3. L has no diagonal elements

Check whether idx is nonzero.

overlap(Graph, subset, level)

Given subset embedded within Graph, compute subset2 such that subset2 contains subset and all of its adjacent vertices.

function update!(p, J::SparseMatrixCSC)

Update the preconditioner p from the sparse Jacobian J in CSC format for the CPU

Note that this implements the same algorithm as for the GPU and becomes very slow on CPU with growing number of blocks.

Add a part of a SparseMatrixCSC column to a SparseVectorAccumulator, starting at a given index until the end.

Returns the number of nonzeros of the L and U factor combined.

Excludes the unit diagonal of the L factor, which is not stored.

For debugging and testing

BlockJacobiPreconditioner

Overlapping-Schwarz preconditioner.

Attributes

• nblocks::Int64: Number of partitions or blocks.
• blocksize::Int64: Size of each block.
• partitions::Vector{Vector{Int64}}:npart` partitions stored as lists
• cupartitions: partitions transfered to the GPU
• lpartitions::Vector{Int64}`: Length of each partitions.
• culpartitions::Vector{Int64}`: Length of each partitions, on the GPU.
• blocks: Dense blocks of the block-Jacobi
• cublocks: Js transfered to the GPU
• map: The partitions as a mapping to construct views
• cumap: cumap transferred to the GPU`
• part: Partitioning as output by Metis
• cupart: part transferred to the GPU

InsertableSparseVector accumulates the sparse vector result from SpMV. Initialization requires O(N) work, therefore the data structure is reused. Insertion requires O(nnz) at worst, as insertion sort is used.

The factor L is stored column-wise, but we need all nonzeros in row row. We already keep track of the first nonzero in each column (at most n indices). Take l = LinkedLists(n). Let l.head[row] be the column of some nonzero in row row. Then we can store the column of the next nonzero of row row in l.next[l.head[row]], etc. That "spot" is empty and there will never be a conflict because as long as we only store the first nonzero per column: the column is then a unique identifier.

SortedSet keeps track of a sorted set of integers ≤ N using insertion sort with a linked list structure in a pre-allocated vector. Requires O(N + 1) memory. Insertion goes via a linear scan in O(n) where n is the number of stored elements, but can be accelerated by passing along a known value in the set (which is useful when pushing in an already sorted list). The insertion itself requires O(1) operations due to the linked list structure. Provides iterators:

ints = SortedSet(10)
push!(ints, 5)
push!(ints, 3)
for value in ints
    println(value)
end