idea: experiment with custom sparse type

[sglyon]

We might want to write a custom sparse data-type for use inside BasisStructure.vals when we have a finite element basis (spline, lin). Here a rough sketch of something that might work

immutable BasisAtPoint{Tv,Ti}
    f_vals::Vector{T}
    inds::UnitRange{Ti}
end

where length(f_vals) == length(inds) --> true and length(f_vals) <= degree_of_spline+1.

We could then collect all of these in a Vector{BasisAtPoint{Tv,Ti}}. When we eventually need to do the matrix operation to evaluate the interpoland we would simply need to do

# let bs.vals <: Vector{BasisAtPoint{Float64,Int}}, for example
function evaluate{Tv}(coefs::Vector{Float64}, bs::BasisStructure{Expanded})
    npoints = length(bs)
    out = Array(Tv, npoints)
    @inbounds for i=1:npoints
        out[i] = dot(bs.vals[i], bs.inds[i], coefs, bs.inds[i])
    end
    out
end

To make this work with minimal change to the current code base (not necessarily something we need to aim for), we would need to define getindex, row_kron, and * for this new type and make Vector{BasisAtPoint} <: AbstractMatrix

memory

This would mean that for each point in the domain where we want to construct a basis structure we would store only:

• the non-zero basis function evaluations at that point (at most k+1 numbers, usually Float64)
• The 2 integers that are start and stop for the UnitRange.

The best we could do using either CSR or CSC is to store the same non-zero basis functions, plus the same number of integers for the indval, plus at least one integer for the indptr.

We can gain memory efficiency here by leveraging the fact that we know the non-zero elements of each row are consecutive. We might be able to achieve the same memory lightness with some block sparse matrix type, but we don't even have the beginnings of that yet. This new data type might be a first step in that direction