Author 
Message 
Susan Margulies science forum beginner
Joined: 28 Jun 2006
Posts: 4

Posted: Wed Jun 28, 2006 6:41 pm Post subject:
Solving largescale sparse binary linear systems EXACTLY?



Hello, everyone! I am just looking for some general advice here.
I have a largescale 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 leastsquares 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

Posted: Wed Jun 28, 2006 11:23 pm Post subject:
Re: Solving largescale sparse binary linear systems EXACTLY?



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 largescale 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 leastsquares
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

Posted: Thu Jun 29, 2006 1:26 am Post subject:
Re: Solving largescale sparse binary linear systems EXACTLY?



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

Posted: Thu Jun 29, 2006 2:41 am Post subject:
Re: Solving largescale sparse binary linear systems EXACTLY?



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

Posted: Thu Jun 29, 2006 7:14 am Post subject:
Re: Solving largescale sparse binary linear systems EXACTLY?



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

Posted: Thu Jun 29, 2006 11:40 am Post subject:
Re: Solving largescale sparse binary linear systems EXACTLY?



Susan Margulies wrote:
Quote: 
I have a largescale 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 COINOR.)
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

Posted: Thu Jun 29, 2006 2:51 pm Post subject:
Re: Solving largescale sparse binary linear systems EXACTLY?



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

Posted: Sun Jul 02, 2006 4:21 pm Post subject:
Re: Solving largescale sparse binary linear systems EXACTLY?



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 unitlower 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 leastsquares 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

Posted: Mon Jul 03, 2006 1:52 pm Post subject:
Re: Solving largescale sparse binary linear systems EXACTLY?



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 unitlower 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 leastsquares 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

Posted: Thu Jul 20, 2006 1:03 pm Post subject:
Re: Solving largescale sparse binary linear systems EXACTLY?



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 unitlower 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), 195207
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 leastsquares solution may be useful to us after all, and is certainly worth pursuing.

The solution of smallest 2norm 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 



The time now is Wed Nov 22, 2017 10:13 pm  All times are GMT

