Re: KKT constraint preconditioner

On 2008-04-23 11:39:30 -0300, laverneth@xxxxxxxxxxx said:

On Apr 23, 4:11 pm, toni.lass...@xxxxxxxxx (Toni Lassila) wrote:
On Wed, 23 Apr 2008 06:31:08 -0700 (PDT), lavern...@xxxxxxxxx wrote:
I want to solve a full KKT system of the form
[A C ]
[CT 0 ]
with A is a n,n matrix, and C is a n,m matrix representing m
constraints on the n primal variables,
and CT is its transpose.

I am trying to solve this method with an iterative method (namely
BiCGSTAB), and thus I need a good preconditioner.
Often, the constraint precondionner is described in the litterature
and I tried to implement it.
It involves approximate solves with the m,m system CT *C. I tried to
use a SAINV factorization on that system which has the great advantage
to avoid forming the matrix CT*C explicitly (see 1) for reference).

However, in my case C has not full column rank and Ct*C is therefore
indefinite and SAINV factorization breaks down because of exactly zero
pivots. Has anyone an idea to avoid such zero pivots in the
factorization ? Should I use an other factorization ?

Why do you have linearly dependent constraints?

I have intersecting interfaces with constraints on dofs on each side
of those interfaces (sliding contact for instance)
Thus at the location where those interfaces cross, some constraints
are linearly dependant from other.
At first sight, considering the way I impose constraints in my models,
it seems complicated to avoid such rendundancy.

Having a problem generate redundant constraints that are awkward, or worse,
to notice is not unusual. That is why there is usually a discussion in
LP books on how to ensure full rank with articial variables. It is often
a minor trick early in the book and never mentioned again although clearly
useful to know.

Such things are more the domain of sci.op-research. Issues of formulation
will often get practical comments there.



.

Relevant Pages

  • Re: KKT constraint preconditioner
    ... use a SAINV factorization on that system which has the great advantage ... indefinite and SAINV factorization breaks down because of exactly zero ... Has anyone an idea to avoid such zero pivots in the ... Why do you have linearly dependent constraints? ...
    (sci.math.num-analysis)
  • Re: KKT constraint preconditioner
    ... use a SAINV factorization on that system which has the great advantage ... Has anyone an idea to avoid such zero pivots in the ... Why do you have linearly dependent constraints? ... usual trick is to add artificial varaibles that are constrained to be ...
    (sci.math.num-analysis)
  • Re: KKT constraint preconditioner
    ... use a SAINV factorization on that system which has the great advantage ... to avoid forming the matrix CT*C explicitly for reference). ... Why do you have linearly dependent constraints? ... I have intersecting interfaces with constraints on dofs on each side ...
    (sci.math.num-analysis)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... i,j,u,v) - IS THERE ANYTHING TO AVOID IT?? ... beginnig to end of tour. ... OBJECTION! ... If you are able to write out all the constraints ...
    (comp.theory)
  • Re: Constraints
    ... you do want to avoid using constraints as much as ... possible and build a dynamic schedule using predecessors and successors. ...
    (microsoft.public.project)