Need help solving highly sparse rectangular matrices over word-size prime fields

[Sucheer Maddury]

Hello, I am doing a project related to discrete logs, and it becomes necessary to solve typical matrix equations
Ax = b
over prime fields. My matrix A will have a large amount of rows (and columns when dense), but HIGHLY sparse. I have tried to enumerate my largest case constraints below:

modulus p: up to 59 bits

A rows: ~150,000

A columns (dense format): ~90,000 (well defined for any given call of course)

Nonzero entries per row: Always under 20 (highly sparse)

b itself is obviously the same height as A itself.

I can guarantee that A has full column rank, highly sparse, and b is completely dense.

Would greatly appreciate design help. I am having a lot of trouble trying to debug and get this to work. I am currently trying block Wiedemann. I sincerely apologize if I am overcomplicating things or if I am not following a standard procedure to do what I would like to do. I am pretty new to this library and would appreciate help regarding which algorithms and domains to use, and proper syntax. My current code, and the momentary error is below.

[includes...]

using Row    = std::vector<std::pair<std::size_t, uint32_t>>;
using Matrix = std::vector<Row>;

using MpzVector = std::vector<mpz_class>;

Matrix M_rows;
MpzVector> X_col;
loadMatrixAndVector("../temp.txt", M_rows, X_col); // own function, populates both

using F60 = Givaro::Modular<int64_t, __uint128_t>;
const size_t m = M_rows.size();

const size_t k = 70; // hardcoded for a specific example here

int64_t q60 = 576460752303423433; // hardcoded for a specific example here

F60 F(q60);

LinBox::SparseMatrix<F60> M(F, m, k);
LinBox::DenseVector<F60>  X(F, m), L(F, k);

for (size_t i = 0; i < m; ++i) {
        for (auto const& [j,eij] : M_rows[i]) {
            typename F60::Element e;
            F.init(e, static_cast<int64_t>(eij));
            M.setEntry(i, j, e);
        }
        int64_t xi = mpz_fdiv_ui(X_col[i].get_mpz_t(), q60);
        F60::Element tmp;  F.init(tmp, xi);
        X[i] = tmp;
    }
    M.finalize();

LinBox::MatrixDomain<F60> MD(F);

LinBox::BlockWiedemannSolver<decltype(MD)> solver(MD);
solver.solve(X, M, L); 

_______________
ERROR (at mulRowSpecialized in /Users/[redacted]/miniconda3/include/linbox/matrix/matrixdomain/matrix-domain.inl:679):
Precondition not met:A.rowdim () == w.size ()
libc++abi: terminating due to uncaught exception of type LinBox::PreconditionFailed
zsh: abort      ./test_u64

[Jean-Guillaume Dumas]

Hello, I would exchange L and M in the solve call: in LinBox results are the first arguments of methods.

Then I would suggest to solve with other methods first on small instances, to check if things work, and then switch to block ones ...

e.g.:

                 solve (L, M, X, Method::SparseElimination());
or

                  solve (L, M, X, Method::Wiedemann());

Regards

[Sucheer Maddury]

Thank you for the response. Sparse Elimination seems to work for some examples I gave, but Wiedemann seems a little flaky. Specifically, I solve my matrix equation over several primes all of which are known to be consistent. Wiedemann solves some and not others, while Sparse Elimination solves all. These prime moduli I tested are in the range of 2 - 32 bits mainly (although I would like to test higher). Would love to know about any limitations of Wiedemann or things I should watch out for. When Wiedemann fails, it returns a generic LinBoxError.

[Sucheer Maddury]

Also, I found that SparseElimination does not work for moduli over 32 bits. Is this a known constraint?

On Thursday, July 24, 2025 at 10:33:09 AM UTC-4 Jean-Guillaume Dumas wrote: