









CMALSSPARSE: Solution of Largescale Least Squares Problems and Systems of Linear
Equations with Sparse Indefinite Matrices.



Systems of linear equations with large sparse matrices are common in
many fields of mathematical modeling and processing of information in
general. Such matrices can have specific properties: they can be positive definite
for some classes of problems (like Finite Element Modeling), or indefinite
in general case. They can also have unequal number of rows and columns. In
case if the number of rows exceeds the number of columns, and the rows are not
linearly dependent, the corresponding system of equations is overdetermined,
so a solution can only be obtained in terms of least squares .
For the solution of large sparse systems with positive definite matrices,
our company developed a very efficient product CMASPARSE, which can solve
systems of several million of equations.
CMALSSPARSE (LS standing for "least squares") is a further development
of the CMASPARSE product. It allows processing of generalcase sparse
matrices, even those arising in overdetermined cases.
There is a number of applications where CMALSSPARSE would be the tool of
choice. One such application is image processing.
This example is an illustration of how the program can be used with
a generalcase sparse matrix, which is not supposed to have any specific
(spectral, etc.) properties. The example is real, and is taken from the image
processing algorithms, when blurred images are restored to a more reasonable
quality, based on the features of pixels surrounding a particular pixel
where more realistic grey hue should be restored.
The image is supposed to be monochromous (grey), and it consists of NbyM pixels,
where N indicates the number of lines, whereas M is the number of columns. As a simple
example, we chose to artificially blur and then deblur a small part of a larger image;
both images are shown below.






The square 64by64 pixels image (shown above) has the total of 4096 pixles. It was
artificially blurred, and then restored using an algorithm that, for each pixel takes
the information from the same line, namely: four pixels to the left and four pixels
to the right.
The global matrix of the system of linear equations will have the dimensions 4096by4096.
It is blockdiagonal, with each block having a particular structure of elements,
where s=1./9., or 0.1111111111111....
Generally speaking, the global matrix is blockdiagonal, each block being an MbyM matrix, as shown below:






The global matrix looks as follows, where the total number of diagonal blocks is N :






It must be emphasized that the program treats this
example as a generalcase sparse matrix, i.e. its
actual structure doesn't matter: the program just receives
the matrix nonzero elements and their indexes onebyone.
Processing of large images leads to a necessity to solve systems
of linear equations of sizes up to hundreds of thousands or even millions.
As an example of a somewhat larger problem than the previous one,
we take blurred version of the full flower
image shown on the left in the example above. The blurred image is then
sharpened using the same algorithm. The toberestored image has
the size of 149 lines by 227 columns.
In this particular instance we created a blurred version of an original image ourselves.
Since the FFT (Fast Fourier Transform) algorithm works with images that must have
numbers or rows and columns being powers of 2, we had to introduce additional
(empty) rows and columns into the original image. Therefore, the blurred image has
the size of 256by256, and the matrix size is 65536.
After the restoration we remove the earlier added rows and columns
in order to bring the restored image to its original size.
CMALSSPARSE solved that system of linear equations in less
than 3 seconds on a computer with QuadCore Intel Celeron processor
N3450 (for the purposes of testing, we deliberately selected a relatively
lowperformance processor, in order to demonstrate that the program is
very efficient in any case).






Our third example is a relatively large image of Moon surface
sized 989by1000. Smaller versions of blurred and restored
images are shown below; we also provide references to the fullsized
images.
Blurred image of original size.
Restored image of original size.










The corresponding linear system contains 1048576 equations.
It has been successfully solved on the same Intel N3450 processor
in 207 seconds. It should be noted that the CPU time used to
solve each particular system may vary significantly, depending on the
such parameters as average number of nonzeros per matrix row,
the matrix condition ratio, etc.


CMALSSPARSE is an absolutely unique tool, suitable for solving
very large (up to several million equations) sparse linear systems with generalcase matrices,
including overdetermined systems.
What makes this product unique ?
You can compile and run it on any modern desktop or laptop computer
(or even on a rather "ancient" PC with Intel Celeron processor).
Incorporation of CMALSSPARSE into you own code is very simple and
straightforward: all internal data structures are located inside the product.
Your code just passes the matrix elements into CMALSSPARSE onebyone,
together with each element's row and colulm indexes; after that you
provide the system's righthand side, and at the end CMALSSPARSE will
return the solution vector.
As soon as a brief (a few seconds) preprocessing completes,
all the solution process is done completely incore, using only the
RAM and the CPU itself. Yes  up to several million of equations with
sparse matrix, on your desktop or even laptop, without any use of
the hard disk during the iterations !
The code is written in standard C and will compile/run on any platform
with a standard C compiler installed.













We invite you to consider using CMALSSPARSE for
your research, development and commercial purposes. You are welcome to
contact us at any time, preferably by email. Our full contact details are provided
here .



CMALSSPARSE is available with
complete source codes and with full commercial lisence allowing easy
incorporation into your own applications.
CMALSSPARSE codes are written in standard C and will compile and run on all UNIX
and Windows platforms without changes. They are also fully commented,
allowing easy modification at user's discretion.
CMALSSPARSE is available on noroyalties and
noannualrenewals basis: there is a oneoff price for an
unlimited commercial lisence.
The product distribution kit includes:
 fullycommented source codes in C;
 and the product's User Instructions containing decriptions of the functions and examples.
To learn more about the full range of our products please follow this
link.
We also invite you to contact us with any questions, preferably by email
on comecau@ozemail.com.au
or
comecau1@bigpond.net.au.





