[Coin-standards] Re: Sparse matrix representation

[Gus Gassmann]

> Good. So why don't we start with the following question:
> 
> What is the best sparse matrix representation to use? The candidates
> that come to mind to me are:
> 
> - The MPS style matrix: i,j, A_ij
> 
> - Compressed Row or Compressed Column. I use CC.
> 
> - Diagonal Band
> 
> - Compressed Diagonal
> 
> - Block Storage plus one of the above

None of the above, at least not quite: 
Block storage. (Given my strong preference for decomposition 
algorithms, I think this is inevitable. You also need to take the 
matrix apart into the different time periods for many other functions.)
Each block should be stored as a "core block" --- leaving aside for 
the moment what that means --- in sparse column form, plus, in 
the case of discrete distributions (with a small number of 
realizations), change blocks, again in sparse column form.
For continuous distributions you ought to store the distributions 
themselves in some suitable format; I haven't come up with a good 
format. (And of course if you have chance constraints, you need 
something else again, and, and. Trouble is, there are so many 
problem variations, and one format to fit all is going to be quite 
complicated.

> Remembering of course that we won't be performing inner products or
> gaussian-type operations on these, but instead a lot of set unions and
> intersections (at least in SMPS). 

This depends on the algorithm you use. If you have a 
decomposition solver, you will very much compute inner products. 
(Of course you are right: If you have a general purpose LP solver, 
you will instead pull full columns out of the data structure for further 
processing, so there will have to be a variety of support procedures, 
too.)



-------------------------------------------------------

gus gassmann          (Horand.Gassmann at dal.ca)

School of Business Administration, Dalhousie University
Halifax, Nova Scotia, Canada , B3H 1Z5
ph. (902) 494-1844
fax (902) 494-1107

http://www.mgmt.dal.ca/sba/profs/hgassmann/