|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
CMA-LS-SPARSE: Solution of Large-scale 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 over-determined,
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 CMA-SPARSE, which can solve
systems of several million of equations.
CMA-LS-SPARSE (LS standing for "least squares") is a further development
of the CMA-SPARSE product. It allows processing of general-case sparse
matrices, even those arising in over-determined cases.
There is a number of applications where CMA-LS-SPARSE 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 general-case 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 N-by-M 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 de-blur a small part of a larger image;
both images are shown below.
|
|
|
|
|
|
|
|
|
|
The square 64-by-64 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 4096-by-4096.
It is block-diagonal, with each block having a particular structure of elements,
where s=1./9., or 0.1111111111111....
Generally speaking, the global matrix is block-diagonal, each block being an M-by-M 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 general-case sparse matrix, i.e. its
actual structure doesn't matter: the program just receives
the matrix non-zero elements and their indexes one-by-one.
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 to-be-restored 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 256-by-256, 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.
CMA-LS-SPARSE solved that system of linear equations in less
than 3 seconds on a computer with Quad-Core Intel Celeron processor
N3450 (for the purposes of testing, we deliberately selected a relatively
low-performance 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 989-by-1000. Smaller versions of blurred and restored
images are shown below; we also provide references to the full-sized
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 non-zeros per matrix row,
the matrix condition ratio, etc.
|
|
|
CMA-LS-SPARSE is an absolutely unique tool, suitable for solving
very large (up to several million equations) sparse linear systems with general-case matrices,
including over-determined 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 CMA-LS-SPARSE 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 CMA-LS-SPARSE one-by-one,
together with each element's row and colulm indexes; after that you
provide the system's right-hand side, and at the end CMA-LS-SPARSE will
return the solution vector.
As soon as a brief (a few seconds) preprocessing completes,
all the solution process is done completely in-core, 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 CMA-LS-SPARSE for
your research, development and commercial purposes. You are welcome to
contact us at any time, preferably by e-mail. Our full contact details are provided
here .
|
|
|
|
|
CMA-LS-SPARSE is available with
complete source codes and with full commercial lisence allowing easy
incorporation into your own applications.
CMA-LS-SPARSE 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.
CMA-LS-SPARSE is available on no-royalties and
no-annual-renewals basis: there is a one-off price for an
unlimited commercial lisence.
The product distribution kit includes:
- fully-commented 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 e-mail
on comecau@ozemail.com.au
or
comecauinfo@gmail.com.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
