2

I plan solving a SLE of a standard form Ax = b, in integers, using LUP-decomposition, using only one thread.

A is a matrix of a size about n3 × 2n3, n ≈ 100 (the more the better though). Matrix is really sparse - each column has only 4 non-zero entries and they all are ±1, each column has n non-zero entries at max. b is also a column with only 4 entries equal ±1.

So, I can get a single solution and then I can add any linear combination (with integer coeff) of vectors from the kernel of A to it to get another solution (I also understand that a basis of that kernel is easy to read from matrix U). I want to find a solution with max c⋅n non-zero entries. I know that normally existence of such a solution is not implied (for a fixed coeff c), but in my case I think there should be one (and not only one). The question is: how do I find it?

P.S. if anybody is willing to provide some solid estimates for runtime of LUP-decomposition + solving part or also estimates for densities of L, U, L\b (solution of Ly = b, matlab-style) and mb even LU\b - I would also be really thankful. Alternatively, any literature about the topic would be helpful as well.

mike239x
  • 205
  • 3
  • 11
  • 1
    The book "Direct Methods for Sparse Linear Systems" by Tim Davis is talking about it. His package that is used inside Matlab, UMFPACK is also can be helpful. For the second part there are also I don't know if you can put a bound on nonzero entries though. I need more info to be able to help. I am happy if I can help you; LU is my thesis :) – Aznaveh Apr 12 '18 at 05:12
  • @Aznaveh I'm a bit slow with the answer, but I wanted to say: thanks for the advice. Can't say that I found the answer to my question in that book, but I realized there is much more to these algorithms. It opened a whole new world to me, in a way :) – mike239x Sep 29 '18 at 15:50

0 Answers0