dense solving over the integers

[Robert Schabinger]

Hi all,

I finally got a chance to run and experiment with Solve.c. However, it appears that, of the three routines that aren't commented out, the only one that is appropriate for solving dense systems is BlasElimination.Unfortunately, if I run over the integers, BlasElimination does not work. I get the warning 

*** WARNING *** 

 You are using a BLAS Domain where your field is not prime

evidently informing me that Method::BlasElimination applies only to fields of prime characteristic. Is there a way to solve dense linear systems over the integers within LinBox? If not, is there a different tool that you would recommend for this purpose?

Best,

Rob

[Robert Schabinger]

Sorry, was my last post too vague? Let me try again. At the command line I typed ./solve <file_with_my_matrix_in_a_supported_dense_format> <file_with_my_vector>. I should also point out that I found that Wiedemann's method seems to cause a runtime error so I went ahead and commented that routine out of the code as well. This is what I got: 

A is 18 by 8

B is [-15860966211741478800203920 8516000687797902226265140 556117983098228206231348864 -299669552714456816188211512 -414546693717519940808983366192 223214102078391286381344822556 608040015347706654891443560256 -327407737459124094341092168184 -243546147304170842702595824 131063624945078165472640676 149895023104398829499946282176 -80714360564035377774941179904 6089942138812263851168587904 -3279294116846006032989484472 -199819644347745790006773328 107534733428206673837146900 202171974403327227814808704 -109063157643891890159410816 ]

Padic Integer Blas-based Solving

Padic Integer Blas-based Solving...

 *** WARNING *** 

 You are using a BLAS Domain where your field is not prime 

 *** WARNING *** 

 You are using a BLAS Domain where your field is not prime 

done (0 s)

Finished activity (rea: 0.01147s, cpu: 0s, sys: 0.004s): done

(BlasElimination) Solution is [0 0 0 0 0 0 0 0 ] / 0

CPU time (seconds): 0.004

Integer CRA Solve

Integer CRA Solve...

  Sparse Elimination Solve In Place

  Sparse Elimination Solve In Place...

    Gaussian elimination with reordering

    Gaussian elimination with reordering...

      Gaussian QLUP elimination on 18 x 8 matrix

      Progress: 0 out of 18 (0.000s elapsed)

      Determinant : 0 over GF (7546571)

      Rank : 8 over GF (7546571)

        done (0 s)

    Finished activity (rea: 0.000387s, cpu: 0s, sys: 0s): done

    Sparse Elimination Lower Triangular Unitary Solve

    Sparse Elimination Lower Triangular Unitary Solve...

        done (0 s)

    Finished activity (rea: 1.502e-05s, cpu: 0s, sys: 0s): done

    Sparse Elimination Upper Triangular Solve

    Sparse Elimination Upper Triangular Solve...

        done (0 s)

    Finished activity (rea: 1.192e-05s, cpu: 0s, sys: 0s): done

    done (0 s)

  Finished activity (rea: 0.0008972s, cpu: 0s, sys: 0s): done

  Sparse Elimination Solve In Place

  Sparse Elimination Solve In Place...

    Gaussian elimination with reordering

    Gaussian elimination with reordering...

      Gaussian QLUP elimination on 18 x 8 matrix

      Progress: 0 out of 18 (0.000s elapsed)

      Determinant : 0 over GF (5169299)

      Rank : 8 over GF (5169299)

        done (0 s)

    Finished activity (rea: 0.0003638s, cpu: 0s, sys: 0s): done

    Sparse Elimination Lower Triangular Unitary Solve

    Sparse Elimination Lower Triangular Unitary Solve...

        done (0 s)

    Finished activity (rea: 1.502e-05s, cpu: 0s, sys: 0s): done

    Sparse Elimination Upper Triangular Solve

    Sparse Elimination Upper Triangular Solve...

        done (0 s)

    Finished activity (rea: 1.097e-05s, cpu: 0s, sys: 0s): done

    done (0 s)

  Finished activity (rea: 0.00088s, cpu: 0s, sys: 0s): done

  Sparse Elimination Solve In Place

  Sparse Elimination Solve In Place...

    Gaussian elimination with reordering

    Gaussian elimination with reordering...

      Gaussian QLUP elimination on 18 x 8 matrix

      Progress: 0 out of 18 (0.000s elapsed)

      Determinant : 0 over GF (6507097)

      Rank : 8 over GF (6507097)

        done (0 s)

    Finished activity (rea: 0.0003572s, cpu: 0s, sys: 0s): done

    Sparse Elimination Lower Triangular Unitary Solve

    Sparse Elimination Lower Triangular Unitary Solve...

        done (0 s)

    Finished activity (rea: 1.502e-05s, cpu: 0s, sys: 0s): done

    Sparse Elimination Upper Triangular Solve

    Sparse Elimination Upper Triangular Solve...

        done (0 s)

    Finished activity (rea: 1.097e-05s, cpu: 0s, sys: 0s): done

    done (0 s)

  Finished activity (rea: 0.0008771s, cpu: 0s, sys: 0s): done

  Sparse Elimination Solve In Place

  Sparse Elimination Solve In Place...

    Gaussian elimination with reordering

    Gaussian elimination with reordering...

      Gaussian QLUP elimination on 18 x 8 matrix

      Progress: 0 out of 18 (0.000s elapsed)

      Determinant : 0 over GF (6777241)

      Rank : 8 over GF (6777241)

        done (0 s)

    Finished activity (rea: 0.00037s, cpu: 0s, sys: 0s): done

    Sparse Elimination Lower Triangular Unitary Solve

    Sparse Elimination Lower Triangular Unitary Solve...

        done (0 s)

    Finished activity (rea: 1.597e-05s, cpu: 0s, sys: 0s): done

    Sparse Elimination Upper Triangular Solve

    Sparse Elimination Upper Triangular Solve...

        done (0 s)

    Finished activity (rea: 1.097e-05s, cpu: 0s, sys: 0s): done

    done (0 s)

  Finished activity (rea: 0.00087s, cpu: 0s, sys: 0s): done

done (0.004 s)

Finished activity (rea: 0.00644s, cpu: 0.004s, sys: 0s): done

(SparseElimination) Solution is [-19 -2 -31 -5 3 -23 -13 7 ] / 1

CPU time (seconds): 0.004

In other words, sparse elimination works fine but blas elimination does not (it returns the zero vector). If I understood correctly, blas elimination was supposed to be a dense solver. My problem is that I would like to have a fast dense solver over the integers for some applications that I am currently working on but LinBox does not seem to have any working support for dense solving over the integers. Is this really the case? Am I missing something? I've attached the files that I used with the Solve.c code available on your website (up to the change commentator -> commentator() necessary to get it to compile with the latest developer release of LinBox).

Best,

Rob

[B Saunders]

Hi, Rob,

Thanks for the sample data.  I've duplicated the problem.  We have two bugs there to track down.

In that example file, if you change from SparseMatrix to BlasMatrix (and include linbox/matrix/blas-matrix.h) and
also change from BlasElimination to Elimination for the method, you will get the answer.

However that is not our most efficient algorithm.  If you are going to do large cases, you need either our BlasElimination to work or IML.  Will let you know when the bug is fixed.

Best,
-dave

--
Prof. B. David Saunders, 302-831-6238, CIS Department, University of Delaware

--
You received this message because you are subscribed to the Google Groups "linbox-use" group.

To view this discussion on the web visit https://groups.google.com/d/msg/linbox-use/-/zkQ4PhS6RtgJ.

To post to this group, send email to linbo...@googlegroups.com.
To unsubscribe from this group, send email to linbox-use+...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/linbox-use?hl=en.

[Robert Schabinger]

Hi All,

I reported these bugs ages ago...any progress? : )

Cheers,

Rob