Solving a large sparse linear system (rectangular & non-full rank) via Wiedemann algorithm

[Taketo Sano]

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.

[B Saunders]

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.

[Taketo Sano]

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.

[Taketo Sano]

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.

[B Saunders]

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.

[Jean-Guillaume Dumas]

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,

On Sep 1, 2019, at 11:27 PM, Taketo Sano <taket...@gmail.com> wrote:

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
____________________________________________________________________

[Taketo Sano]

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
____________________________________________________________________

[Taketo Sano]

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.

[B Saunders]

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.