TAUCS has LDL^t decomposition for indefinite matrices -
taucs_ccs_factor_ldlt - but this routine is not multifrontal and as a
results it is very slow.
TAUCS has also LU for asymmetric matrices - taucs_ooc_factor_lu - only
out-of-core - but the performance also is not that good.
So, basically TAUCS is very good for symmetric positive definite
matrices only (you must specify only a half of the matrix). If this is
not the case, I would recommend UMFPACK.
I wrote the BeBOP Sparse Matrix Converter:
http://bebop.cs.berkeley.edu/smc/
specifically to do these kinds of format conversions -- you are
welcome to use it.
mfh
This would be a
good idea. However, please note that the sparse matrices are very
different, so this should be considered as a very rought estimate. My
experience is with matrices from FEM - if your matrices are different,
then the answer could differ.
Briefly. TAUCS is for positive
definite. MUMPS (not UMFPACK) for the rest. At present I use basically
MUMPS only, as for positive definite it is comparable with TAUCS. Yet,
there was a discussion on the MUMPS list that for some matrix, UMFPACK was
better than MUMPS. In my experience for FEM, MUMPS is better.
This week I am on vacation, so my activity on this list will be
small.
mfh
It would be good to find some example, that is, a matrix that one has
already made. Alternatively to use Mathematica or Matlab to construct such
a matrix by hand. This would help a lot to develop a code. To debug a code
without having an example/benchmark is hard.
I would advise first prototyping with something like Mathematica/Matlab -
producing examples - and only then programming in C/C++ and using examples
from the previous step for debugging.
That's right, any matrix with that structure is not positive definite.
Suppose a vector x has the block structure
x = [ 0
x_2 ]
where x_2 is nonzero. Then if A is your matrix, x^T A x = 0. That
means A can't be positive definite.
> Can TAUCS still handle a matrix like this? If not, which
> solver do you recommend? The authors of the paper claimed to use a
> "direct (LU) sparse matrix solver", which I suspect TAUCS implements
> (not sure tho').
You can use LU, or a symmetric indefinite solver (LDL^T factorization).
mfh
You may also want to look at
FREELY AVAILABLE SOFTWARE FOR LINEAR ALGEBRA ON THE WEB (September 2006)
http://www.netlib.org/utk/people/JackDongarra/la-sw.html
Recently on NA Digest he has promised to update this table.
TAUCS implements Cholesky decomposition. One can consider it as a
special case of LU for a symmetric positive definite matrix. But it is
applicable only for a symmetric positive definite matrix.
I do not have MATLAB and to check what you have done I would prefer to
have a matrix in the Matrix Market format. Could you please save it in
MATLAB in the Matrix Market format? The code to do it is at
http://math.nist.gov/MatrixMarket/formats.html#MMformat
Then if this works with the Matrix Market - I can check it quickly, then
something is wrong with the matrix.
Please note that you file contains not a half but the full matrix. I
have not found what TAUCS does in this case but the code enclosed
(test_mtx.cpp) is working by me. I have used taucs_ccs_read_ijv -
taucs_ccs_read_mtx was giving the wrong number of columns. The output is
as follows
10
taucs_ccs_read_ijv: allocating 12500 ijv's
taucs_ccs_read_ijv: allocating 15625 ijv's
taucs_ccs_read_ijv: read ConstraintMatrix.mmf, n=428
428 428
20
30
40
Elimination tree depth is 217
Symbolic Analysis of LL^T: 4.10e+004 nonzeros,
4.79e+006 flops, 4.39e+005 bytes in L
Relaxed Analysis of LL^T: 5.03e+004 nonzeros,
7.12e+006 flops, 5.63e+005 bytes in L
Symbolic Analysis = 0.000 seconds
(0.000 cpu)
sivan 110 94
LL^T Factorization: Matrix is not positive definite.
nonpositive pivot in column 423
Supernodal Multifrontal LL^T = 0.015 seconds
(0.000 cpu)
50
taucs_ccs_factor_ldlt: starting n=428
taucs_ccs_factor_ldlt: done; nnz(L) = 4.10e+004, flops=9.57e+006
60
That is, Cholesky fails but LDL^T seems to work. It would be safer to
feed not the full matrix but only its half but hopefully TAUCS ignores
exra matrix components. But I do not know - have never done it.
This is a conflict between two different runtime libraries. Presumably
the code and libraries are compiled with different switches. Have you
compiled the code with /MD?
Was you able to compile other test TAUCS programs previously? This code
should be compiled the same way as samples at
http://matrixprogramming.com/TAUCS/
I thought that you have managed to compile them. Haven't you?
Woah, that's broken.
The Sparse Matrix Converter has both read and write routines, if
you're interested.
mfh
btw if you have questions specific to the Sparse Matrix Converter,
please e-mail them to me directly, rather than to this list -- I don't
want to distract the ever-diligent Evgenii from his work :)
mfh
Try to use some file name, say ttt. If this helps, then it is necessary
to learn how in your settings to write to stdout. Or just check this
file after the run.
Do not worry. It is a fun for me to answer questions from the list, when
I have time. For the last two years I am working as a sales engineer
multiphysics and I miss programming a bit.
I believe that this is NET specific. You have written that you were able
to compile the original example. You have to find out when you start
receiving this message.
I have heard that in NET there are two type of functions - internal and
external. Is it correct? I guess that TAUCS should be an external
application.
I have not seen problems with taucs_ccs_factor_llt_mf and
taucs_ccs_factor_llt_ll. They can fail if
1) The matrix is not positive definite,
2) There is not enough memory
Please try to make working
taucs_logfile("filename")
Then you should see in the filename some information from which you will
see the reason.
Yes, you prepare your matrix wrong. From the TAUCS manual
"In symmetric and hermitian matrices we store only one triangle,
normally the lower one. Most of the routines fail if their argument
contain the upper triangle of a symmetric/hermitian matrix."
In you case you use correct attributes
A.flags = (TAUCS_DOUBLE | TAUCS_SYMMETRIC | TAUCS_LOWER);
but in the matrix there are triples where i < j. This is the beginning
of your matrix
1 1 1
426 1 0.949684
427 1 -4.89074
428 1 -0.422826
429 1 1
2 2 1
426 2 1.05071
427 2 -5.37836
428 2 -0.467804
429 2 1
3 3 1
2 3 0.451894
and the last entry is wrong. It should be
3 2 0.451894
And there are many such wrong entries. So you have a crash, as promised.