Sparse Vectors

VL contains both a sparse vector type, which stores only the non-zero elements of the vector, and a sparse matrix type, whose rows are sparse vectors. Sparse vectors can be efficiently combined with other sparse vectors or normal vectors using the standard vector operations:

    SparseMatf sm;
    SparseVecf sv1, sv2, sv3;
    Vecf  v;

    v = sm * v;
    sm[0] += v;
    sv1 = sv2 + sv3;

Initialisation

Sparse vectors are typically initialised by giving a list of index, element pairs:

    SparseVecf sv;      // unsized sparse vector
    SparseVecf sv(20);  // zero vector of length 20.
    SparseVecf sv(5, 1, 1.0, 2, 2.0, VL_SV_END);
                        // the vector [0.0, 1.0, 0.0, 0.0 4.0]

The standard vector initialisers can also be used.

Manipulation

Once you have your sparse vector, it can be changed in the following ways:

* Re-initialise with the SetElts() method:

    sv.SetSize(5);
    sv.SetElts(1, 1.0, 4, 4.0, VL_SV_END);
    // sets sv to [0.0, 1.0, 0.0, 0.0 4.0]

* Use the SVIter[fd] iterator, which lets you iterate over the elements of a sparse vector, and access them using the methods:

j.Data() : returns the current element's data
j.Index() : returns the current element's index

Note: It is highly recommended that you use the SVIter[fd] class to manipulate sparse vectors, as it is written to be as efficient as possible, even performing a binary search for elements when necessary. The iterator class can be used in a number of ways:

* Use Begin(), Inc(), AtEnd() to iterate over the non-zero elements of the vector:

    SVIterf j;
    // sv = sv * 2
    for (j.Begin(sv); !j.AtEnd(); j.Inc())
        j.Data() *= 2.0;

* Use one of the following methods:

  Inc(Int i)    moves on to elt i, where i will increase by 1 on each call
  IncTo(Int i)  moves on to elt i, where i will increase monotonically

within another for-loop to access the elements of the sparse vector corresponding to i. For example:

    // v = v + sv
    for (j.Begin(sv), i = 0; i < v.NumItems(); i++)
    {
        j.Inc(i);
        v[i] += j.Data();

    }

    // a += dot(sv1, sv2)
    for (j.Begin(sv2), k.Begin(sv1); !k.AtEnd(); k.Inc())
    {
        j.IncTo(k.Index());  // find corresponding elt in sv2
        if (j.Exists())
            a += j.Data() * k.Data();
    }

* Use the Overlay() method: a.Overlay(b) performs a[i] = b[i] for all non-zero b[i].

* Direct access: Begin(), AddElt() or AddNZElt() new element pairs in order, then call End(). (Use AddNZElt() if you know for certain the added element will be non-zero.) For example:

    // set sv to [0.0, 1.0, 0.0, 0.0 4.0]
    sv.NumElts(5);
    sv.Begin();
    sv.AddNZElt(1, 1.0);
    sv.AddNZElt(4, 4.0);
    sv.End();

* As a last resort, use the Get() and Set() methods. These calls are not efficient for multiple accesses, but will at least perform a binary search to locate the requested element quickly.

    sv1.Set(10, sv2.Get(20)); // sv1[10] = sv2[20]

Note: The best way to write code for sparse vectors and matrices is to use the SVIter[fd] class, and recast code to use the efficient vector operations where possible.

Sparse Fuzziness

The SparseVec class has a tolerance level for elements to be considered zero, referred to as the fuzz. (If |x| < fuzz, it is treated as zero.) This can be set with the method SparseVec[fd]::SetFuzz(fuzz). The default value of fuzz is 1e-10.

A convenient way to test if an element is zero according to the current fuzz setting is to use the SparseVec[fd]::IsNonZero(elt) method.

Back to VL