Thread Subject: Sparse integer LU decomposition

Hi everyone,

I was wondering if there is the possibility to perform sparse integer LU decomposition preferably with full pivoting?

I've tried to convert to intX and invoke lu(), but an error message is displayed. I would really appreciate any help or hints concerning this.

Thanks a lot,

Pascal

On 8 Des, 17:26, "Pascal Schulthess" <pascal.schulth...@biologie.hu-
berlin.de> wrote:
> Hi everyone,
>
> I was wondering if there is the possibility to perform sparse integer LU decomposition preferably with full pivoting?
>
> I've tried to convert to intX and invoke lu(), but an error message is displayed. I would really appreciate any help or hints concerning this.

Depends on what you mean by 'sparse integer LU decomposition'.
If you mean 'perform an LUD on a sparse matrix which elements
are integers' then yes, it is perfectly possible.

If you mean 'perform an LUD where the result is sparse and
which non-zero elements are integers' then no:

- The LUD of a sparse matrix is in general not sparse.
- The LUD of an integer matrix does in general not
  contain integers.

Rune

"Pascal Schulthess" <pascal.schulthess@biologie.hu-berlin.de> wrote in
message news:jbqof0$4bk$1@newscl01ah.mathworks.com...
> Hi everyone,
>
> I was wondering if there is the possibility to perform sparse integer LU
> decomposition preferably with full pivoting?
>
> I've tried to convert to intX and invoke lu(), but an error message is
> displayed. I would really appreciate any help or hints concerning this.

You can't have sparse integer type matrices in MATLAB.

Even if you could, LU is not defined for integer types in MATLAB (the
elements of the factors would likely be noninteger values.)

What would you use this functionality to do if it were available? Perhaps
there's an alternate way to achieve your goal using functionality that is
available in MATLAB.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

"Steven_Lord" <slord@mathworks.com> wrote in message <jbqp41$6n1$1@newscl01ah.mathworks.com>...
>
>
> "Pascal Schulthess" <pascal.schulthess@biologie.hu-berlin.de> wrote in
> message news:jbqof0$4bk$1@newscl01ah.mathworks.com...
> > Hi everyone,
> >
> > I was wondering if there is the possibility to perform sparse integer LU
> > decomposition preferably with full pivoting?
> >
> > I've tried to convert to intX and invoke lu(), but an error message is
> > displayed. I would really appreciate any help or hints concerning this.
>
> You can't have sparse integer type matrices in MATLAB.
>
> Even if you could, LU is not defined for integer types in MATLAB (the
> elements of the factors would likely be noninteger values.)
>
> What would you use this functionality to do if it were available? Perhaps
> there's an alternate way to achieve your goal using functionality that is
> available in MATLAB.
>
> --
> Steve Lord
> slord@mathworks.com
> To contact Technical Support use the Contact Us link on
> http://www.mathworks.com

Ok, let me be a little more precise:

Not, I have a large sparse matrix and perform lu decomposition. Ideally, I'd like to convert this sparse matrix to integer and then perform lu. And if I would have three wishes, the resulting matrices would also be sparse and integer :)

But, ok, from you're answers I'm getting that this will not be possible. Perhaps I gotta look into UMFPACK be T. Davis or just ask him if he knows something :)

"Pascal Schulthess" <pascal.schulthess@biologie.hu-berlin.de> wrote in
message news:jbqq94$am9$1@newscl01ah.mathworks.com...
> "Steven_Lord" <slord@mathworks.com> wrote in message
> <jbqp41$6n1$1@newscl01ah.mathworks.com>...
>>
>>
>> "Pascal Schulthess" <pascal.schulthess@biologie.hu-berlin.de> wrote in
>> message news:jbqof0$4bk$1@newscl01ah.mathworks.com...
>> > Hi everyone,
>> >
>> > I was wondering if there is the possibility to perform sparse integer
>> > LU decomposition preferably with full pivoting?
>> >
>> > I've tried to convert to intX and invoke lu(), but an error message is
>> > displayed. I would really appreciate any help or hints concerning this.
>>
>> You can't have sparse integer type matrices in MATLAB.
>>
>> Even if you could, LU is not defined for integer types in MATLAB (the
>> elements of the factors would likely be noninteger values.)
>>
>> What would you use this functionality to do if it were available? Perhaps
>> there's an alternate way to achieve your goal using functionality that is
>> available in MATLAB.
>>
>> --
>> Steve Lord
>> slord@mathworks.com
>> To contact Technical Support use the Contact Us link on
>> http://www.mathworks.com
>
> Ok, let me be a little more precise:
>
> Not, I have a large sparse matrix and perform lu decomposition.

That you can do with LU, although as Rune said the factors may not
themselves be sparsely populated. If you do this, you'll probably want to
use the three, four, or five output syntaxes.

http://www.mathworks.com/help/techdoc/ref/lu.html

> Ideally, I'd like to convert this sparse matrix to integer and then
> perform lu.

No can do for the two reasons I stated above.

> And if I would have three wishes, the resulting matrices would also be
> sparse and integer :)

If S is sparse then the outputs L and U from [L, U] = lu(S) will also be
stored as sparse matrices, though again they may not be sparsely populated.
That'll probably depend on the structure of the matrix whose decomposition
you're trying to compute.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

"Steven_Lord" <slord@mathworks.com> wrote in message
> What would you use this functionality to do if it were available? Perhaps
> there's an alternate way to achieve your goal using functionality that is
> available in MATLAB.

Ok, my problem statement is to find the left null space of a large sparse matrix. With large I mean in the order of 10,000x17,000. This matrix only has whole number entries and the null space too should only have whole number entries.

"Pascal Schulthess" wrote in message <jcci5k$mem$1@newscl01ah.mathworks.com>...
> "Steven_Lord" <slord@mathworks.com> wrote in message
> > What would you use this functionality to do if it were available? Perhaps
> > there's an alternate way to achieve your goal using functionality that is
> > available in MATLAB.
>
> Ok, my problem statement is to find the left null space of a large sparse matrix. With large I mean in the order of 10,000x17,000. This matrix only has whole number entries and the null space too should only have whole number entries.

This sounds related somewhat to Euclidian's division algorithm:
 http://en.wikipedia.org/wiki/Euclidean_algorithm

For sparse null space (but float vectors), LU is a wrong choice, rather using QR:
http://www.mathworks.com/matlabcentral/fileexchange/27550-sparse-null-space-and-orthogonal.

You might approximate the float results by the rational forms, then put them in common denominator. I expect you will get a null space with HUGE whole numbers, that can only be manipulated with formal calculation.

Bruno