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

[Andreas Waechter]

Hi Sivan,

Many thanks for the good news!  Since the solution of the linear system is
usually the computational bottleneck, we are very interested to try and
include alternative codes for that task.

It would be great if you could add the inertia computation to TAUCS and
send me the changed code (or make it available).  I will be happy to write
the interface to TAUCS.  Since I have to attend a few other things first,
this might not happen within the next two weeks, but I will try to do it
as soon as I find time for it.

As usual I would ask users of Ipopt that would like to use TAUCS (once we
have tested and approved it) to obtain it separately from your website and
put the source code (or the compiled library) into a certain directory,
since we cannot offer third party code on COIN.  If I understand your
license correctly, there is no restriction regarding the use, also not for
commercial purposes, correct?

Many thanks again for letting us know about TAUCS.

Regards,

Andreas


On Thu, 11 Sep 2003, Sivan Toledo wrote:

>
> 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
>
> _______________________________________________
> Coin-ipopt mailing list
> Coin-ipopt at www-124.ibm.com
> http://www-124.ibm.com/developerworks/oss/mailman/listinfo/coin-ipopt
>