FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » num-analysis
Solving large-scale sparse binary linear systems EXACTLY?
Post new topic   Reply to topic Page 1 of 1 [10 Posts] View previous topic :: View next topic
Author Message
Susan Margulies
science forum beginner


Joined: 28 Jun 2006
Posts: 4

PostPosted: Wed Jun 28, 2006 6:41 pm    Post subject: Solving large-scale sparse binary linear systems EXACTLY? Reply with quote

Hello, everyone! I am just looking for some general advice here.

I have a large-scale sparse underdetermined binary system (actually, it consists of 1s, 0s, and -1s), and I would like to solve it exactly (meaning a rational solution).

I know this is going to be a bit of a bear... is there anything that will make it easier? I think most of the libraries like SPARSKIT and UMFPACK solve the linear system by returning the least-squares optimization, and that is not what I need.

Are there any papers or libraries that someone could direct me too? I know C and C++ but no Fortran...

Thanks for your help! I really appreciate it! I have a large linear system waiting to be solved and an advisor breathing down my neck. :)

Best,
Susan
Back to top
Robert B. Israel
science forum Guru


Joined: 24 Mar 2005
Posts: 2151

PostPosted: Wed Jun 28, 2006 11:23 pm    Post subject: Re: Solving large-scale sparse binary linear systems EXACTLY? Reply with quote

In article <9402013.1151520139986.JavaMail.jakarta@nitrogen.mathforum.org>,
Susan Margulies <smargulies@ucdavis.edu> wrote:
Quote:
Hello, everyone! I am just looking for some general advice here.

I have a large-scale sparse underdetermined binary system (actually, it
consists of 1s, 0s, and -1s), and I would like to solve it exactly
(meaning a rational solution).

I know this is going to be a bit of a bear... is there anything that
will make it easier? I think most of the libraries like SPARSKIT and
UMFPACK solve the linear system by returning the least-squares
optimization, and that is not what I need.

Don't ask a numerical analysis newgroup if you need an exact rational
solution.

You might try Maple. For example:

with(LinearAlgebra):
A:= RandomMatrix(500,1000,density=0.01,generator=-1..1):
for i from 1 to 500 do A[i,i]:= 1 od:
# this to make it probable that A has full rank
b:= RandomVector(500):
ti:= time(): S:= LinearSolve(A,b):
time()-ti;

It solved this example in 6.984 seconds on my computer.

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
Back to top
Susan Margulies
science forum beginner


Joined: 28 Jun 2006
Posts: 4

PostPosted: Thu Jun 29, 2006 1:26 am    Post subject: Re: Solving large-scale sparse binary linear systems EXACTLY? Reply with quote

Quote:
Don't ask a numerical analysis newgroup if you need
an exact rational solution.

Of course I quite understand that at first glance, asking a numerical analysis group for an exact solution is a bit odd. But on the other hand, the people here are the ones with the real expertise in solving linear systems, and I'm sure they know the existing software packages and their pros and cons inside and out. If anyone can direct me, I think they would be reading here!

Quote:
You might try Maple.

Of course that it is the first choice, and my initial application prototype is written in Maple. But unfortuneatly, I am now dealing that matrices that are 1/2 million by 1/2 million (give or take a couple of 100 thousand rows/colums here and there), and Maple (although I love it!) is just too slow.

My matrices are EXTREMELY sparse, and as I mentioned earlier, they are underdetermined and only consist of 1s, -1s and 0s. I only need one solution, and I can just set all the free variables to 0 and take whatever bubbles up. I'm sure that someone somewhere has already done this... maybe I could modify an algorithm in an existing library? Or implement an algorithm written up in some obscure paper?

Advice from the experts would be appreciated. :)

Best,
Susan

PS> I have taken your advice, and posted elsewhere too. Thank you for your comments!
Back to top
A..L.
science forum beginner


Joined: 17 May 2006
Posts: 15

PostPosted: Thu Jun 29, 2006 2:41 am    Post subject: Re: Solving large-scale sparse binary linear systems EXACTLY? Reply with quote

On Wed, 28 Jun 2006 21:26:48 EDT, Susan Margulies
<smargulies@ucdavis.edu> wrote:

Quote:
Don't ask a numerical analysis newgroup if you need
an exact rational solution.

Of course I quite understand that at first glance, asking a numerical analysis group for an exact
solution is a bit odd. But on the other hand, the people here are the ones with the real expertise
in solving linear systems, and I'm sure they know the existing software packages and their pros
and cons inside and out. If anyone can direct me, I think they would be reading here!


Ask on sci.math.symbolic

A.L.
Back to top
Han de Bruijn
science forum Guru


Joined: 18 May 2005
Posts: 1285

PostPosted: Thu Jun 29, 2006 7:14 am    Post subject: Re: Solving large-scale sparse binary linear systems EXACTLY? Reply with quote

Susan Margulies wrote:

Quote:
My matrices are EXTREMELY sparse, [ ... ]

Instead of insisting that people help you with that horrible matrix,
it could help if you tell us where that matrix comes from. I mean:
perhaps it's possible not to formulate the problem in matrix terms.
And if not: it might help if that matrix has a specific structure,
such as being banded or so.

Han de Bruijn
Back to top
Arnold Neumaier
science forum Guru


Joined: 24 Mar 2005
Posts: 379

PostPosted: Thu Jun 29, 2006 11:40 am    Post subject: Re: Solving large-scale sparse binary linear systems EXACTLY? Reply with quote

Susan Margulies wrote:
Quote:

I have a large-scale sparse underdetermined binary system (actually, it consists
of 1s, 0s, and -1s), and I would like to solve it exactly (meaning a rational
solution).

Introduce an additional variable x_0 to make the system homogeneous,
and then put
min x_0
s.t. Ax=0, x_0>=1, x_i integral
to a good mixed integer LP solver; they can handle sparsity.
(Try a code from COIN-OR.)
If you know additional constraints, impose them, too - this may make
the task much easier.

Whether you can handel 200000 unknowns is not that clear, but if
anything can do it then such an approach.


Arnold Neumaier
Back to top
Peter Spellucci
science forum Guru


Joined: 29 Apr 2005
Posts: 702

PostPosted: Thu Jun 29, 2006 2:51 pm    Post subject: Re: Solving large-scale sparse binary linear systems EXACTLY? Reply with quote

In article <2734554.1151544438866.JavaMail.jakarta@nitrogen.mathforum.org>,
Susan Margulies <smargulies@ucdavis.edu> writes:
Quote:
Don't ask a numerical analysis newgroup if you need
an exact rational solution.

Of course I quite understand that at first glance, asking a numerical analysis group for an exact solution is a bit odd. But on the other hand, the people here are the ones with the real expertise in solving linear systems, and I'm sure they know the existing software packages and their pros and cons inside and out. If anyone can direct me, I think they would be reading here!

You might try Maple.

Of course that it is the first choice, and my initial application prototype is written in Maple. But unfortuneatly, I am now dealing that matrices that are 1/2 million by 1/2 million (give or take a couple of 100 thousand rows/colums here and there), and Maple (although I love it!) is just too slow.

My matrices are EXTREMELY sparse, and as I mentioned earlier, they are underdetermined and only consist of 1s, -1s and 0s. I only need one solution, and I can just set all the free variables to 0 and take whatever bubbles up. I'm sure that someone somewhere has already done this... maybe I could modify an algorithm in an existing library? Or implement an algorithm written up in some obscure paper?

Advice from the experts would be appreciated. :)

Best,
Susan

PS> I have taken your advice, and posted elsewhere too. Thank you for your comments!

there is a version of Gaussian elimination known as "divisionfree".
it simply goes by multiplying the rows in the remaining system to be
reduced to upper triangular form by suitable integers such that elimination
simply results from subtraction. this saves the division to the very final step,
that means you get the x(i) as fractions of integers. if your system is
underdetermined you can perform this also, setting the free variables to zero and
computing one special solution in this way. but there is a problem with this:
within m steps your coefficients may grow up from 1 as 2^m and for m=100000 this
requires long integer arithmetic which makes it slow.
hth
peter
Back to top
Susan Margulies
science forum beginner


Joined: 28 Jun 2006
Posts: 4

PostPosted: Sun Jul 02, 2006 4:21 pm    Post subject: Re: Solving large-scale sparse binary linear systems EXACTLY? Reply with quote

Thank you everyone for your comments! There are now lots of directions for me to look, which is wonderful.

Here is one way of using UMFPACK that I came up with that is not very good:

Goal: Solve Ax = b, where A is large, sparse and underdetermined (m x n with n > m).

1) Using UMFPACK factoring, get PAQ = LU, where P,Q are permutation matrices and L is unit-lower triangular, and U is upper triangular. Write LU = L[U1 | U2] where L is m x m, and U1 is m x m and U2 is m x (n - m)

2) Ax = b -> PAQQ'x = Pb -> Q'x = y. Here comes the leap of faith: Then, if you write y = (y_1 0) where y_1 is of size m, and the other n - m entries are zero, I can try and solve:

LU1y_1 = Pb

This is a square system, which UMFPACK can solve. If it is consistent, then I have a solution. However... U1 is just upper triangular, which means it is not necessarily invertible. Thus, this system may not have a solution, while the original Ax = b does.

I would love to hear comments or other ideas, if people are interested and have the time. Smile

I also had a nice chat with my advisor, and it turns out that the least-squares solution may be useful to us after all, and is certainly worth pursuing.

So another question I have, is how to use UMFPACK to get the least squares solution of an underdetermined system?

I know the factoring PAQ = LU will be used, but I'm not sure exactly how. Maybe take the transpose somehow?

Anyway, thank you to everyone who posted. I really appreciate that you took the time to share your thoughts, and it will take me awhile to sort through all of the ideas. :)

Best,
Susan
Back to top
Peter Spellucci
science forum Guru


Joined: 29 Apr 2005
Posts: 702

PostPosted: Mon Jul 03, 2006 1:52 pm    Post subject: Re: Solving large-scale sparse binary linear systems EXACTLY? Reply with quote

In article <20342703.1151857301342.JavaMail.jakarta@nitrogen.mathforum.org>,
Susan Margulies <smargulies@ucdavis.edu> writes:
Quote:
Thank you everyone for your comments! There are now lots of directions for me to look, which is wonderful.

Here is one way of using UMFPACK that I came up with that is not very good:

Goal: Solve Ax = b, where A is large, sparse and underdetermined (m x n with n > m).

1) Using UMFPACK factoring, get PAQ = LU, where P,Q are permutation matrices and L is unit-lower triangular, and U is upper triangular. Write LU = L[U1 | U2] where L is m x m, and U1 is m x m and U2 is m x (n - m)

2) Ax = b -> PAQQ'x = Pb -> Q'x = y. Here comes the leap of faith: Then, if you write y = (y_1 0) where y_1 is of size m, and the other n - m entries are zero, I can try and solve:

LU1y_1 = Pb

This is a square system, which UMFPACK can solve. If it is consistent, then I have a solution. However... U1 is just upper triangular, which means it is not necessarily invertible. Thus, this system may not have a solution, while the original Ax = b does.

I would love to hear comments or other ideas, if people are interested and have the time. :)

I also had a nice chat with my advisor, and it turns out that the least-squares solution may be useful to us after all, and is certainly worth pursuing.

So another question I have, is how to use UMFPACK to get the least squares solution of an underdetermined system?

I know the factoring PAQ = LU will be used, but I'm not sure exactly how. Maybe take the transpose somehow?

Anyway, thank you to everyone who posted. I really appreciate that you took the time to share your thoughts, and it will take me awhile to sort through all of the ideas. :)

Best,
Susan

in order to avoid your trouble with U1, you must introduce column interchanges
but this could have an tremendous impact on the sparsity of the decomposition.
there exists also work on a sparse QR decomposition, and this could resolve
your problem, but you should not hope for wonders: the sparse QR will be much less
sparse than the sparse LU. (Using the QR decomposition you can define
a basic least squares solution immediately)
also, it is not clear to me how to recover an exact solution from this (and from
umfpack) do you hope that roundoff will be so modest that rounding the numerical
solution to the nearest integer already gives you the answer, esppecially if you
rely on a basic least squares solution?
hth
peter
Back to top
Arnold Neumaier
science forum Guru


Joined: 24 Mar 2005
Posts: 379

PostPosted: Thu Jul 20, 2006 1:03 pm    Post subject: Re: Solving large-scale sparse binary linear systems EXACTLY? Reply with quote

Susan Margulies wrote:
Quote:
Thank you everyone for your comments! There are now lots of directions for me to look, which is wonderful.

Here is one way of using UMFPACK that I came up with that is not very good:

Goal: Solve Ax = b, where A is large, sparse and underdetermined (m x n with n > m).

1) Using UMFPACK factoring, get PAQ = LU, where P,Q are permutation matrices and L is unit-lower triangular, and U is upper triangular. Write LU = L[U1 | U2] where L is m x m, and U1 is m x m and U2 is m x (n - m)

2) Ax = b -> PAQQ'x = Pb -> Q'x = y. Here comes the leap of faith: Then, if you write y = (y_1 0) where y_1 is of size m, and the other n - m entries are zero, I can try and solve:

LU1y_1 = Pb

This is a square system, which UMFPACK can solve.
If it is consistent, then I have a solution.

It will be consistent if the original system has full rank.

But a numerical solution will not be exact, usually. You can use a
rounding routine like that in
W. Huyer and A. Neumaier,
Integral approximation of rays and verification of feasibility</B>,
Reliable Computing 10 (2004), 195-207
http://www.mat.univie.ac.at/~neum/papers.html#rays
to try to convert it into rational. But this will work only if
the integers in the rational representartion are small, and there is
no guarantee for that.

Quote:
I also had a nice chat with my advisor, and it turns out that the least-squares solution may be useful to us after all, and is certainly worth pursuing.

The solution of smallest 2-norm has the form x=A^Ty, where AA^Ty=b is
the solution of a square positive semidefinte system. If you have
a QR factorization of A^T you can get x as x=Qz where R^Tz=b.

Again, the solution will be only approximate and you need to make it
rational by a rounding routine.

Arnold Neumaier
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [10 Posts] View previous topic :: View next topic
The time now is Wed Oct 18, 2017 4:46 pm | All times are GMT
Forum index » Science and Technology » Math » num-analysis
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Linear operator and determinant aline Math 0 Wed Nov 29, 2006 2:37 am
No new posts Conservation of Info. and Generation of Info. give "Systems" Zim Olson Math 0 Thu Jul 20, 2006 7:53 pm
No new posts Psychotronic Weapons Systems - Physical Principles Jack Sarfatti Math 0 Mon Jul 17, 2006 10:46 pm
No new posts Complexity of Sparse Cholesky Factorization crazyFritz Research 0 Mon Jul 17, 2006 2:24 pm
No new posts Complexity of Sparse Cholesky Factorization crazyFritz Math 5 Mon Jul 17, 2006 1:31 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0274s ][ Queries: 16 (0.0046s) ][ GZIP on - Debug on ]