Path: news.mathworks.com!not-for-mail
From: "Tim Davis" <davis@cise.ufl.edu>
Newsgroups: comp.soft-sys.matlab
Subject: Re: curious problem with sparse matrices that have explicit "0" entries.....
Date: Sat, 3 Jan 2009 23:59:02 +0000 (UTC)
Organization: University of Florida
Lines: 73
Message-ID: <gjou46$45r$1@fred.mathworks.com>
References: <Xns9B885ED987C87ejhericholtmamcom@216.168.3.30>
Reply-To: "Tim Davis" <davis@cise.ufl.edu>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1231027142 4283 172.30.248.35 (3 Jan 2009 23:59:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sat, 3 Jan 2009 23:59:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 45902
Xref: news.mathworks.com comp.soft-sys.matlab:509714


"Eric J. Holtman" <ejh@ericholtman.com> wrote in message <Xns9B885ED987C87ejhericholtmamcom@216.168.3.30>...
> 
> 
> I've run into a quirky problem with MATLAB having to 
> do with sparse matrices built elsewhere (in a C++ program)
> and linprog.
> 
> The datafile for this can be downloaded at
> 
> http://www.ericholtman.com/sparse_error.mat
> 
> If you download that file, and then attempt to solve the
> linear program with the command:
> 
> [x fval exitflag output] = linprog (f, A, b, Aeq, beq, lb, ub);
> 
> you get the following error:
> 
> Exiting: cannot converge because the primal residual, dual residual,
>  or upper-bound feasibility is NaN.
> 
> however, if you do
> 
> A = sparse(full(A));
> Aeq = sparse(full(Aeq));
> 
> and then re-run the command, it succeeds, with fval =  1.5185e+003.
> 
> I built this problem in C++, and transferred the data into
> MATLAB using the mx* and eng* functions.
> 
> As an artifact of construction, some of the entries in the
> A and Aeq matrices are explicitly 0.
> 
> I don't understand why this causes a problem......  why
> should there be any difference between a sparse matrix
> with say, 17 non-zero entries, and one with the same 17
> non-zero entries, and an 18th with an explicit zero?
> 
> Note that I can change my C++ program to not store the
> explicit zeros, and everything works perfectly, without
> having to do the x = sparse(full(x)); conversion.  I've
> run it with huge arrays, so am I 100% convinced that I
> am setting up the sparse array correctly (so that I know
> I'm setting up the offsets in the PR, IR and JC arrays
> correctly.)
> 
> I'm just curious as to why linprog would fail with a 
> sparse matrix that has explicit zeros?
> 
>  


A valid MATLAB sparse matrix cannot have any explicit zeros.

"find" is doing the right thing in this case, though ... it's finding
the entries of the matrix.  "find" (and all of MATLAB) assumes
that the input matrices are all valid (no explicit zeros, for example).
What's broken is the matrix, not "find".

I'm not sure why linprog would fail, but I'm not too surprised.
Some MATLAB operations work fine on invalid matrices (with
explicit zeros) and some do not.

Try the "spok" mexfunction on the File Exchange to test your
sparse matrix.  It will tell you if it has other invalid properties or not.
It should also detect the presence of explicit zeros, if I wrote it correctly...

Now, I would argue that it's a pity MATLAB doesn't allow explicit
zeros (they happen quite naturally, when solving a nonlinear
system for example).  But given the design decision it would be
pretty tough to change it now, since so much of MATLAB assumes
the matrix has no explicit zeros.