I agree that generic or otherwise container-insensitive algorithms are
going to be a big help and should be actively pursued. However, I
think your statement is a bit too strong. There are formats for laying
out sparse arrays in memory that are reasonably sensible, efficient,
and at least in some cases can be extended to distributed machines;
Yale, MSV/DMSV, etc. These may well provide a basis for reusable
non-generic algorithms. The main requirement is that the representation
be accessible at a low level. While it's true that one of the main
principles of object-oriented programming is hiding the representation,
there are situations in which the representation *is* important, and
getting one's job done always takes precedence over doctrinal purity.
That's why standard string provides a conversion to char *. (There
*were* strong objections to this from purists on X3J16.)
>
> > Having said this, I also agree that now is not the time to
> > standardize array classes. We should either wait for a de facto
> > (or de jure - maybe valarray will be more useful than people now
> > expect) standard to emerge, or at least wait and see how
> > template-expression based implementations are working out in
> > practice.
>
> I do not believe there will ever be a useful "standard numeric
> container", "standard array class", etc. I think we as a community
> should quit biding our time on this issue, and just learn to write
> code that is generic with respect to the numeric container type, in
> the same way that the STL is generic with respect to the data
> structures that its algorithms operate on.
As much as I agree that STL is beautiful and to be emulated, I think
this statement is too strong. The obvious advantages of generic
algorithms don't preclude settling on some standard representations
of certain containers.
Note the use of the word _representations_. You may be correct that no
one _class_ will be widely adopted. I'm not sure this is necessary as
long as the representation is directly accessible.
My reasoning is this. There often really _is_ a "best" algorithm to
solve a particular problem. For example, no one solves very large,
sparse, symmetric positive definite systems of equations using any
algorithm other than conjugate gradient. (There is plenty of room for
debate on which preconditioner is best, of course.) No one sorts a
large, randomly ordered set of data using anything but quicksort. No
one searches an ordered table using anything but a binary search. It
isn't a matter of taste; the choice of algorithm is constrained by the
real mathematical properties of the problem. In some cases, for a
sufficiently well-defined set of problems and operation costs, a
particular algorithm can be _proven_ to be the most efficient. It's
the computational equivalent of a Carnot cycle. Likewise, there may
really be a "best", or at worst a few "best", representations for
various kinds of mathematical objects. I contend that standards for
representations may indeed emerge (whether de facto or de jure is not
important), and I point to the existence of widely accepted layouts for
sparse arrays, such as Yale or MSR, in support of this contention.
A matrix class, on the other hand, is simply one possible
implementation of a particular representation of the mathematical
object we call a matrix. (A meta-representation, if you like being
cute.) While there may be advantages to MSR (for example) as a
representation of a sparse matrix, arising from basic mathematical
principles, the precise _spelling_ of the various parts of the class
interface is completely irrelevant to the inherent utility of the
class. If my class lays out a sparse matrix in Yale format, it really
doesn't matter whether I spell the transpose operation as Transpose() or
Tr(). I can feed my matrix to any algorithm that expects Yale format,
so long as the algorithm expects the matrix to be at the other end of a
pointer to double and my class gives me a way to generate such a
pointer.
>
> The STL covers a different domain than numeric algorithms, but its
> library design techniques are accessible, extensible, exemplary, and
> replicable. We should start doing it.
I agree completely. I just hate to see us completely toss the idea
that representations are significant and amenable to standardization.
>
> --
> Geoffrey Furnish email: furnish@lanl.gov
> LANL XTM Radiation Transport/POOMA phone: 505-665-4529 fax: 505-665-5538
>
> "Software complexity is an artifact of implementation." -Dan Quinlan
>
Perhaps I'm now sinking to the level of picking nits, but this not one
of the more intelligent things I've heard Dan say. Complexity is *not*
an artifact of the implementation. H-adaptive finite element algorithms
are complex no matter how you spell them.