[Coin-ipopt] Re: TAUCS and COIN/Ipopt

[Sivan Toledo]

Andreas,

A year ago we didn't have such a code, but now we actually do (almost).
We now have a new factorization routine in the code that factors A=L*D*L^T 
where L is lower triangular and D is block diagonal with 1-by-1 and 2-by-2 
blocks. I believe that this is exactly the same factorization that the 
Harwell routine uses. This factorization preserves inertia (D has the same 
inertia as A), so all we have to do to get the inertia is to compute the 
eigenvalues of D, which is trivial. We currently do not compute the inertia, 
but I can add an option to do that in a few days.

Our  routine is new, not yet well optimized, and not as well tested as our 
Cholesky routines, but this will probably be fixed in a few weeks (it's not 
that slow, about half the speed of our Cholesky routine, but we can probably 
make it faster). We actually wrote this factorization routine as an 
intermediate step toward out-of-core symmetric indefinite factorization (for 
eigensolvers), but solving the KKT systems that you have is also a good 
application for it, especially since you need the inertia.

Our library is actually mostly sequential, only one routine is currently 
parallel, and the default compilation always generates a sequential library, 
so that shouldn't be a problem. You won't need MPI or pthreads when you call 
the library or when you link Ipopt.

I'll be happy to work with you on any integration issues that might arise.

I think that the best way to proceed is for me to first implement the 
inertia-computation routine, and then to send you the new code. While you do 
the integration, I can work on improving performance.

Regards, Sivan

On Thursday 11 September 2003 05:39, Andreas Waechter wrote:
> Dear Sivan,
>
> Many thanks for your message and the update on TAUCS.
>
> We have not added an interface to TAUCS in Ipopt.  But we are still very
> interested in alternative linear solvers that might be of use for Ipopt.
>
> The sparse matrix that we need to factorize is of the form
>
>  /  H   A \
>  \ A^T  0 /
>
> i.e. it is symmetric, but indefinite.  The requirement on the linear
> solver is that is needs to be able to tell us the inertia of this system
> after factorization, i.e. how many positive and negative eigenvalues the
> matrix has.  The Harwell routines provide this information.
>
> Does your solver compute the inertia during the factorization?  I had a
> look at the documentation, and on the first sight it seemed to me that it
> doesn't.  Is that correct?  (I assume that the option for TAUCS used in a
> linear interior point method that you mention in your message does not
> refer to the above system, but rather one of the form A^T D A ...?)
>
> Unfortunately, I only know of the Harwell routines as direct linear
> solvers for symmetric indefinite systems that compute the inertia.  It
> would be great to be able to offer more alternatives in Ipopt, in
> particular even a parallel code like yours.
>
> Do you think this is something your code can or could do? Any comments
> would be welcome.  I'm also sending this message to the mailing list in
> case someone else has some ideas.
>
> Thanks again,
>
> Andreas
>
> On Wed, 10 Sep 2003, Sivan Toledo wrote:
> > Dear Andreas and Kirk,
> >
> > I found a discussion between you two on a mailing list from about a year
> > ago about replacing MA27 with my code, TAUCS, in COIN/Ipopt. I am curious
> > to know whether anything came out of that idea.
> >
> > I would like to mention two things: First, when Yifan Hu of Wolfram
> > Research added TAUCS to Mathematica 5, he modified the sparse cholesky
> > factorization code slightly in order to allow it to solve semidefinite
> > systems that arise in iterior point algorithms (by replacing diagonal
> > values near 0 with large values, which effectively drops the
> > corresponding equation and variable from the system). I have not
> > incoroporated his modification into the main code, but I'll be happy to
> > do so if you need such functionality in order to use TAUCS in COIN/Ipopt.
> >
> > Second, I have made improvements in the code over the summer. The main
> > changes that might have a positive impact on you if you have not yet done
> > the integration, is a clean build on many more OS's (including linux,
> > irix, solaris, Windows, MacOS, and freeBDS; I don't have an up-to-date
> > AIX or HPUX systems, but it shouldn't be hard to build on them), and an
> > easy way to configure the library. The configuration support should allow
> > you to build automatically a version of TAUCS with just the functionality
> > that you need, say only the real double-precision sparse Choleksy code.
> >
> > Regards, Sivan Toledo
> >
> > ------------------------
> > Prof. Sivan Toledo
> > School of Computer Science
> > Tel-Aviv University
> > Tel-Aviv 69978, Israel
> > Phone: +972-3-640 5285
> > Fax:   +972-3-640 9357
> > Email: stoledo at tau.ac.il
> > Web:   http://www.tau.ac.il/~stoledo