45 views

Skip to first unread message

Sep 2, 2019, 8:07:38 AM9/2/19

to linbox-use

Hello, I am new to LinBox.

I am trying to solve a sparse linear system via Wiedemann algorithm.

For our case the matrix A is large (n, m > 10,000) rectangular and necessarily not full-rank.

Is there a way to solve Ax = b via Widemann algorithm?

I tried `solve(x, A, b, Method::Blackbox());` for a simple case which actually has a solution,

but the library reported `bad preconditioner` while computing the minimal polynomial, and could not get a solution.

A = [

1, 0, 1, 0;

0, 1, 1, 1;

0, 0, 0, 0;

1, 1, 0, 1;

1, 0, 1, 0

]

b = [1; 1; 0; 0; 1]

( x = [1; 1; 0; 0] is one solution )

Thanks in advance.

Sep 2, 2019, 11:11:36 AM9/2/19

to linbo...@googlegroups.com

These points could affect the suggestion:

1. Is the problem over GF2?

2. What is the density? Average number of entries per row, say.

3. Do you know the system is consistent?

4. Is An arbitrary solution acceptable or do you need a random sample of the solution space?

Sent from my iPhone

--

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

To unsubscribe from this group and stop receiving emails from it, send an email to linbox-use+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/linbox-use/7b321e2b-c924-4944-9279-55c2b83d0b46%40googlegroups.com.

Sep 3, 2019, 8:35:34 AM9/3/19

to linbox-use

Thank you for the reply. Sorry I haven't supplied enough information.

1. Is the problem over GF2?

yes.

2. What is the density? Average number of entries per row, say.

Here is one example:

rows = 53,325

cols = 65,370

nnz = 445,030

density = (nnz / rows * cols) = 0.0001276673780415868

I want to tackle larger systems, if possible.

3. Do you know the system is consistent?

Necessarily not.

4. Is An arbitrary solution acceptable or do you need a random sample of the solution space?

Yes, an arbitrary solution is acceptable.

In fact, the question is whether the system has a solution or not (the actual solution is not necessary).

Currently I am using LU-decomposition to solve this problem.

Thanks!

To unsubscribe from this group and stop receiving emails from it, send an email to linbo...@googlegroups.com.

Sep 5, 2019, 3:09:17 AM9/5/19

to linbox-use

I should have asked the question this way:

Can we effectively use Wiedemann algorithm to determine the consistency of a large sparse rectangular linear system over GF2,

rather than using LU decomposition and finding the actual solution?

Any advice would be appreciated.

Thank you.

Sep 5, 2019, 9:37:45 AM9/5/19

to linbo...@googlegroups.com

I've been slow to respond, sorry.

I do think that for your density Wiedemann's method is likely to be better than elimination (though you could try the sparse elimination method in LinBox). In fact I am going to recommend the block Wiedemann method. In fact, your consistency problem over GF2 is precisely the problem for which Coppersmith created the block Wiedemann method.

For the system Ax = b, one strategy is to compute the rank of the two matrices A and (A,b). With a Wiedemann method the two rank computations can be expected to take about 4/3 the time of a solver call. However they don't depend on as strong preconditioning, the problem you encountered.

Regarding the pragmatics of using LinBox, while I've not recreated the exact preconditioned problem you encountered, I have run into several bugs. The convenient solutions and examples in LinBox are primarily for problems over larger fields and over the integers. I'm encountering bugs in trials over tiny fields. By the way, are you using a release or the developer "bleeding edge" from GitHub?

As it happens, I'm currently working on a rank problem over GF3. I think I can shortly offer you a code fragment for using block Wiedemann based on what I have there.

To unsubscribe from this group and stop receiving emails from it, send an email to linbox-use+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/linbox-use/ec925dcf-a837-4fa9-b1eb-0cb7a07e1336%40googlegroups.com.

Sep 5, 2019, 9:41:41 AM9/5/19

to linbo...@googlegroups.com

On 05/09/2019 09:09, Taketo Sano wrote:

I should have asked the question this way:

Can we effectively use Wiedemann algorithm to determine the consistency of a large sparse rectangular linear system over GF2,rather than using LU decomposition and finding the actual solution?

Dear Taketo Sano, several problems have been corrected in the current git version.

With your example and the current master I have

A is 5 by 4

[[1, 0, 1, 0 ], [0, 1, 1, 1 ], [0, 0, 0, 0 ], [1, 1, 0, 1 ], [1,
0, 1, 0 ]]

B is [ [1 1 0 0 1 ]]

solve.wiedemann.modular...

...

solve.wiedemann.modular (0.000555038 s)

Solution is [ [1 1 0 0 ]]

CHECK

Regards,

Hello, I am new to LinBox.I am trying to solve a sparse linear system via Wiedemann algorithm.

For our case the matrix A is large (n, m > 10,000) rectangular and necessarily not full-rank.Is there a way to solve Ax = b via Widemann algorithm?

I tried `solve(x, A, b, Method::Blackbox());` for a simple case which actually has a solution,but the library reported `bad preconditioner` while computing the minimal polynomial, and could not get a solution.

A = [1, 0, 1, 0;0, 1, 1, 1;0, 0, 0, 0;1, 1, 0, 1;1, 0, 1, 0]

b = [1; 1; 0; 0; 1]

( x = [1; 1; 0; 0] is one solution )

-- Jean-Guillaume Dumas. ____________________________________________________________________ Jean-Guill...@univ-grenoble-alpes.fr Tél.: +33 457 421 732 Professeur, Université Grenoble Alpes. Fax.: +33 457 421 828 Laboratoire Jean Kuntzmann, Mathématiques Appliquées et Informatique 700 avenue centrale, IMAG - CS 40700, 38058 GRENOBLE cedex 9, FRANCE http://ljk.imag.fr/membres/Jean-Guillaume.Dumas ____________________________________________________________________

Sep 5, 2019, 10:51:09 AM9/5/19

to linbox-use

Thank you very much for the instructions.

The version I am using is 1.6.3 (found in Makefile.am).

I installed it on my Mac via linbox-auto-install.sh .

I will try again with the master branch on git.

Thanks.

-- Jean-Guillaume Dumas. ____________________________________________________________________ Jean-Guil...@univ-grenoble-alpes.fr Tél.: +33 457 421 732 Professeur, Université Grenoble Alpes. Fax.: +33 457 421 828 Laboratoire Jean Kuntzmann, Mathématiques Appliquées et Informatique 700 avenue centrale, IMAG - CS 40700, 38058 GRENOBLE cedex 9, FRANCE http://ljk.imag.fr/membres/Jean-Guillaume.Dumas ____________________________________________________________________

Sep 5, 2019, 10:45:15 PM9/5/19

to linbox-use

I installed the current git version, and was able to get the correct solution.

However, I cannot get the correct rank; it returns 0 or gets caught into a infinite loop.

Can you point out if there is something wrong in my code?

```

typedef Givaro::Modular<double> Field;

typedef GaussDomain<Field>::Matrix Matrix;

typedef DenseVector<Field> Vector;

Field F(2);

Matrix A(F, rows, cols);

// set entries for A

A.write(std::cout << "A:", Tag::FileFormat::Maple) << ';' << std::endl;

Vector b(F, rows);

// set entries for b

b.write(std::cout << "b:", Tag::FileFormat::Maple) << ';' << std::endl;

Vector x(F, cols);

solve(x, A, b, Method::Wiedemann()); // I get a correct solution.

size_t r;

rank(r, A, Method::Wiedemann()); // something is wrong here.

std::cout << "rank: " << r << std::endl;

x.write(std::cout << "x:", Tag::FileFormat::Maple) << ';' << std::endl;

```

Another question:

Mr Saunders proposed to use the BlockWiedemann algorithm, so I tried, but got an error by the following code:

```

solve(x, A, b, Method::BlockWiedemann());

```

```

solve.block-wiedemann.modular...

BlockWiedemannSolver (Warning) : block size too large, number of tries might be large

ERROR (at mulRowSpecialized in /usr/local/include/linbox/matrix/matrixdomain/matrix-domain.inl:679):

Precondition not met:A.rowdim () == w.size ()

```

Could you tell me how I can properly use this method?

Thank you.

Sep 6, 2019, 9:26:54 AM9/6/19

to linbo...@googlegroups.com

Until we fix method Wiedemann for small primes both solve and rank will be unreliable. In the meantime you can do this:

typedef Givaro::GFqDom<int32_t> Field;

Field F(2, 10); // GF(2^10)

to get results (a bit slower than we'd like).

--

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

To unsubscribe from this group and stop receiving emails from it, send an email to linbox-use+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/linbox-use/4a365eb0-f4f9-4dfb-95b2-8de2d929bd55%40googlegroups.com.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu