Search   Memberlist   Usergroups
 Page 1 of 1 [10 Posts]
Author Message
Arnold Neumaier
science forum Guru

Joined: 24 Mar 2005
Posts: 379

Posted: Thu Jul 20, 2006 1:03 pm    Post subject: Re: Solving large-scale 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 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
Peter Spellucci
science forum Guru

Joined: 29 Apr 2005
Posts: 702

Posted: Mon Jul 03, 2006 1:52 pm    Post subject: Re: Solving large-scale 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 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
Susan Margulies
science forum beginner

Joined: 28 Jun 2006
Posts: 4

 Posted: Sun Jul 02, 2006 4:21 pm    Post subject: Re: Solving large-scale 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 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
Peter Spellucci
science forum Guru

Joined: 29 Apr 2005
Posts: 702

Posted: Thu Jun 29, 2006 2:51 pm    Post subject: Re: Solving large-scale 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
Arnold Neumaier
science forum Guru

Joined: 24 Mar 2005
Posts: 379

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

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

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

Arnold Neumaier
Han de Bruijn
science forum Guru

Joined: 18 May 2005
Posts: 1285

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

Susan Margulies wrote:

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

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
A..L.
science forum beginner

Joined: 17 May 2006
Posts: 15

Posted: Thu Jun 29, 2006 2:41 am    Post subject: Re: Solving large-scale 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!

A.L.
Susan Margulies
science forum beginner

Joined: 28 Jun 2006
Posts: 4

Posted: Thu Jun 29, 2006 1:26 am    Post subject: Re: Solving large-scale 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

Robert B. Israel
science forum Guru

Joined: 24 Mar 2005
Posts: 2151

Posted: Wed Jun 28, 2006 11:23 pm    Post subject: Re: Solving large-scale 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 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
Susan Margulies
science forum beginner

Joined: 28 Jun 2006
Posts: 4

 Posted: Wed Jun 28, 2006 6:41 pm    Post subject: Solving large-scale sparse binary linear systems EXACTLY? 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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [10 Posts]
 The time now is Tue Mar 26, 2019 4:41 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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