[CppAD] Format for sparse Jacobians/Hessians

[Robert P. Goddard]

Intel's web site, at

http://software.intel.com/sites/products/documentation/hpc/compilerpro/en-us/cpp/win/mkl/refman/appendices/mkl_appA_SMSF.html

describes a large number of sparse matrix formats that are efficient for
input to sparse solvers and other standard operations. The trouble with
all of them is that the function that fills them must proceed in strict
row-major or column-major order. Backtracking would be very expensive.
Now, I don't know exactly how the innards of a function like
get_sparse_hessian would work within CppAD, but I suspect that elements
would get built up as they are encountered in the tape, not in any
particular index order. If that's true, it seems to me that the
evaluation pretty much has to be in terms of triplets. I have used a
std::map<std::pair<size_t,size_t>,Value_type> successfully, with
reasonable speed.

Admittedly, a "map" format is very poor for most subsequent matrix
operations. That is often the case: Structures that are good for one
phase of a data-set's lifetime are poor for another phase. But that's
OK, because traversing a std::map in row or column order is easy and
fast, so it can be transformed into any of the "standard" formats trivially.

The focus of CppAD is the first phase, creating the sparse matrix. The
best choice of the representation for the next phase depends critically
on what the client software needs to do next. Hence, unless that next
operation is to be part of the CppAD library, CppAD should stay out of
that debate. Choose a "filling" format that is efficient for filling the
matrix, and let the application code transform it to a "working" format
if that makes sense, in preparation for whatever comes next.

Bob Goddard