[petsc-dev] Solving under determined systems

Munson, Todd tmunson at mcs.anl.gov
Wed Sep 21 21:20:46 CDT 2016

You can set up TAO to solve such a problem.

However, your problem boils down to solving the 
linear system

  w - V*lambda = 0
  V'*w         = b

Taking the Schur complement with respect to w, you get 
the system

  V'*V*lambda = b

You then form and invert V'*V, which is a 5x5 matrix 
and recover w = V*lambda.

That will get you the least 2-norm solution for your 
underdetermined system.

LSQR will solve the underdetermined system and give
you the least norm solution if you don't want to
do the matrix-matrix product and inverse.  LSQR
may also be more stable.  See


That site suggests using CRAIG in the underdetermined
case, but I don't know if CRAIG is implemented 
in PETSc.

Other norms are more difficult to obtain, but can 
be done.  One and infinity norms are recast as
linear programming problems.  Matrix norms are
equality constrained quadratic programs.
p-norms with p >= 1 are convex
nonlinear programs.


> On Sep 21, 2016, at 8:24 PM, Mark Adams <mfadams at lbl.gov> wrote:
> I thought least squares was for tall skinny (overdetermined) solves? I have a short fat (5 x ~100) matrix to solve.
> On Wed, Sep 21, 2016 at 4:24 PM, Stefano Zampini <stefano.zampini at gmail.com> wrote:
> Mark,
> You can use KSPLSQR
> Stefano
> Il 21 set 2016 11:21 PM, "Mark Adams" <mfadams at lbl.gov> ha scritto:
> I want to solve for w in V' w = b, where V is tall and skinny. So a short fat matrix "solve". This is underdetermined. I would like to minimize the two norm (or any norm) of w. This looks like an optimization problem, would TAO do this?
> Mark

More information about the petsc-dev mailing list