🚀 go-pugleaf

on Mon, 9 Oct 89 08:23:00 EDT,
dl@g.oswego.edu (Doug Lea) said:

dl> > Any further news on the Matrix class?  I think I noticed that in 1.36
dl> > (on labrea.stanford.edu), this was moved into the wish list.

dl> The Matrix classes that I was working on have run up against some very
dl> difficult intrinsic performance problems that I am trying to solve via
dl> some work on otherwise unrelated tools and compilation strategies.
dl> (Some of these were hinted at in some of my comp.lang.c++ postings
dl> this summer.) In the meantime, Tom Keffer
dl> (keffer@blake.acs.washington.edu), Stephen Pope (scp@sfi.santafe.edu),
dl> and Robert Davies (SRWMRBD@wnv.dsir.govt.nz) all have or will have
dl> some very good, but less general (an asset!) and/or differently
dl> structured freely available Matrix packages. Check them out.  Someday,
dl> a libg++ Matrix package will be available, but I refuse to release the
dl> current classes, partly because they are in disarray, but mostly
dl> because I believe that they are unsuitable for serious heavy-duty
dl> computation. Stay tuned for news on other fronts that will hopefully
dl> alleviate such problems.

dl> -Doug

Its true, there are others out there working on it despite the serious
impedements to implementing a truly good system.  If all continues well,
I should be releasing *take 2* of a vector/matrix package that I first
wrote about a year ago, and has been in constant use in a large
time series analysis program written in C++.  That is to say,
*take 1* works, and has been rather thoroughly tested/debugged.
The purpose of *take 2* is to implement some ideas for improved
efficiency/genericity that have come through another year of experience
with C++ and many fruitful discussions with dl.

The package is far from ideal.  For those unfamiliar with the
difficulties in implementing a vector/matrix package, here are
a few of them:  1) avoidance of the creation of unneccessary
intermediate vectors or matrices (hereafter called ``objects'')
in expressions, 2) the closely related problem of idempotency/non-
idempotency (see dl's comp.lang.c++ postings in May and June on this
topic), 3) proper class hierarchy design to reduce virtual/indirection
overhead, 4) code design lending itself to vectorization/optimization,
and 5) providing a rich enough set of types (i.e. triangular, diagonal,
sparse, sub- and indexed- matrix variants.

There are additionally choices to be made about semantics:  does
one create things that are treated as objects (i.e. Matrix a,b; ...
a.add(b)), as symbols (references), or as values.  The latter two
options lend themselves more directly to the sort of algebraic
expressions we'd like to be able to write in our code, but choosing
between them imposes many efficiency costs.

In my code, priority has been assigned to the avoidance of
unneccessary temporary generation, and to constructor/object
semantics that skirt around the idempotency problem, with a slight
preformance cost that can be avoided by optionally using a few
supplied tricks (ie. Matrix Func() { Matrix t; ... return t.release(); }).
The _horrible_ truth is that I use reference counting...
I must point out thought, that these decisions were made with our
particular application in mind - working with large, dense matrices
(anywhere from 10x10 to 10000x10000), where data copying is to be
avoided at all costs, and ease of submatrixing of crucial importance.
These would not be the choices I would make for 2x2 or 3x3 matrices.
Also, I developed all of this on sparc machines; I would have made many
different choices if I'd being working on a vax, for example.

I'll certainly post when I've got something to hand out; if there's
any of you who'd like to see the stuff a little earlier, and to help
work it out/over, please drop me a line.

Stephen Pope
Santa Fe Institute
scp@sfi.santafe.edu

Aside from Matrix routines, I'd be eager to see a nice elegant class
for implementing Graphs.  A Graph of Xs, connected by Ys, appears in
almost as many programs as a Queue of Xs or a Set of Ys.  For example,
a Graph of Cities (Nodes) and Highways (Edges), might support
operations of the following sort:

	Graph G;
	.
	.
	.
	Node node1 = G.nodes[1];
	int i = node1.indegree();
	Edge edge1 = node1.outedges[i-1]; // take last outgoing edge...
	(edge1.to).inedges -= edge1;    // unlink it...
	node2.inedges += edge1;         // and link to node2  
	float c = (edge1.contents)->cost;
	long pop = (node1.contents)->population;
	Highway *hwy49 = edge1.contents;
	NodeQueue visitme = node1.traveling_salesman_tour();

Ok, so the last one isn't that essential.  And we rarely see one-way
highways, but...

The idea is that the connectivity is reflected in the Graph class,
while the semantics of the edges and nodes is captured in two separate
classes, and accessed through a single ptr stored in the Nodes/Edges.
The Graph class would have to be supplemented by Node and Edge
classes, where most of the work would take place.

It's easy to write an ugly class definition (as I've just done this
weekend), but an elegant one would greatly simplify an ENORMOUS number
of programs.  Anyone have one?  Anyone interested in writing one?
Anyone want to give this to their class as a homework?

Wishfully,
Othar Hansson
othar@ernie.berkeley.edu