Re: Matrix inversion tool

[Shlomi Fish]

Hi Omer,

On Mon, Aug 10, 2015 at 8:56 PM, Omer Zak w...@zak.co.il wrote:

 All those discussions about inverting matrices over Z2 make me curious
 to know what kind of problems can be solved by inverting such matrices.

 I suppose that the actual problem, with which Shachar is struggling, is
 proprietary information. However, is it possible to indicate the kind of
 problems which can be attacked by inverting a matrix over Z2?


Some examples for such problems are
http://www.shlomifish.org/MathVentures/toggle_squares.html and the similar
puzzle of http://www.logicgamesonline.com/lightsout/daily.php . Hope it
helps!

Regards,

-- Shlomi

-- 
--
Shlomi Fish http://www.shlomifish.org/

Chuck Norris helps the gods that help themselves.

Please reply to list if it's a mailing list post - http://shlom.in/reply .
___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Omer Zak]

All those discussions about inverting matrices over Z2 make me curious
to know what kind of problems can be solved by inverting such matrices.

I suppose that the actual problem, with which Shachar is struggling, is
proprietary information. However, is it possible to indicate the kind of
problems which can be attacked by inverting a matrix over Z2?

--- Omer



On Sun, 2015-08-09 at 19:50 +0300, Shachar Shemesh wrote:
 On 09/08/2015 13:29, Matan Ziv-Av wrote:
 
  On Sun, 9 Aug 2015, Oleg Goldshmidt wrote:
   Shachar Shemesh shac...@shemesh.biz writes: 
Hi all, I'm looking for a tool/code to invert a matrix. So far,
this sounds trivial. I have one special requirement. I did not
think it was too special, except I could not find anywhere that
supplied it. I want the matrix to be over a different field
(i.e. - not the real numbers). In my particular case, I want it
to be over Z2 (zero and one).
[... snipped ...]


-- 
The brain does not use addresses.  www.werner-seyfried.com
My own blog is at http://www.zak.co.il/tddpirate/

My opinions, as expressed in this E-mail message, are mine alone.
They do not represent the official policy of any organization with which
I may be affiliated in any way.
WARNING TO SPAMMERS:  at http://www.zak.co.il/spamwarning.html


___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Matan Ziv-Av]

On Mon, 10 Aug 2015, Oleg Goldshmidt wrote:


I assure you I read and understood Omer's and your posts. If you go back
to my reply you will surely realize that at no point I contradicted
you. I just pointed out that you didn't need to divide (by det(A)==1),
which would lead to the problem you correctly point out.


Here's what Omer actually asked:

What happens if you use the regular matrix inversion tool which works 
on real numbers?


And I explained that a regular matrix inversion tool will return a 
result that cannot be converted back to Z_2. If you are using another 
tool, you do not have the option to not divide by the determinant, 
since that too returns the actual inverse matrix after the division by 
the determinant (though, it never actually divides by the determinant).



Friends again? ;-)


Obviously, I have no personal problems with you. I just don't like 
incorrect information (about a subject I really care about) available, 
since it has a way of returning very unexpectedly.


To show that there is no animosity, I'll answer your other questions:


273x273 seems quite
large for a regular computer. It is not clear to me (I'll appreciate a
comment just for curiousity's sake as well as for education) that a
straightforward algorithm will be practical.


At the end of this message is a python program with simple 
implementations of both algorithms (Gauss eliminiation and recursive). 
Run them for sizes 10 to 16 consecuitively to see how the difference 
between exponential and polynomial is very significant in this case.


Then run for 273 (or 2730, for that matter), to see that with the right 
algorithms, 273x273 is very small for a computer.


If you save it as x.py, run as
./x.py n k s
Where n is the number of rows, k is the expected number of non-zeros in 
a row, and the optional s is a seed for the pseudo-random number 
generator.


The output is the determinant by GE and the time it takes, and then the 
determinant by the recursive method and then the time it takes.


The optimizations you suggested are possible (for both algorithms), but 
they are all just scaling the time needed. Even if you speed up by a 
factor of 10^9, the recursive algorithm will just not work.


The sparsity of the matrix does not help much. If there are (on average) 
k non-zero entries per line, you get O(k^n) instead of O(n!).



[*] I strongly suspect you read too much into Omer's use of the word
   real (also used in the OP).


Actually he said real numbers. How can you read it in any other way? 
especially in this context.







--
Matan.

#!/usr/bin/python

import random
import sys
import time
import copy

def mat(n,p):
return [[int(random.random()p) for e in range(n)] for e in range(n)]

def id(n):
return [[int(i==j) for i in range(n)] for j in range(n)]

def ExchangeLines(m,i,j):
m[i],m[j] = m[j],m[i]

def AddLines(m,i,j):
n=len(m)
m[i] = [ (m[i][k]+m[j][k])%2 for k in range(n)]

def ge(a,b):
n=len(a)
for i in range(n):
for j in range(i,n):
if a[j][i]!=0:
ExchangeLines(a,i,j)
ExchangeLines(b,i,j)
break
if a[i][i]==0:
return 0
for j in range(n):
if j!=i:
if a[j][i]!=0:
AddLines(a,j,i)
AddLines(b,j,i)
return 1

def minor(a,i,j):
b=copy.deepcopy(a)
b.pop(i)
for x in b:
x.pop(j)
return b

def recdet(a):
n=len(a)
if n==1:
return a[0][0]
s=0
for i in range(n):
if a[0][i]!=0:
s=(s+recdet(minor(a,0,i)))%2
return s


n=int(sys.argv[1])
p=float(sys.argv[2])
if len(sys.argv)=4:
random.seed(int(sys.argv[3]))

a1=mat(n,p/n)
a2=copy.deepcopy(a1)
b=id(n)

s=time.clock()
print d1=,ge(a1,b)
e=time.clock()
print e-s

s=time.clock()
print d2=,recdet(a2)
e=time.clock()
print e-s



___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Shachar Shemesh]

On 10/08/15 20:56, Omer Zak wrote:
 All those discussions about inverting matrices over Z2 make me curious
 to know what kind of problems can be solved by inverting such matrices.

 I suppose that the actual problem, with which Shachar is struggling, is
 proprietary information. However, is it possible to indicate the kind of
 problems which can be attacked by inverting a matrix over Z2?
I think I'm not letting on too much by giving the broad area.

When calculating RAID-6 parity, one of the common methods is called
erasure coding. You have n data blocks in a stripe which you need to
write to n+p actual disks, such that for any number of failures up to p,
you can recover the original n data blocks.

One of the ways to do that is by employing a family of algorithms called
Erasure codes, the most famous of which is Reed Solomon. The basic
idea is that you write a matrix which is n over n+p, and you multiply
the n data blocks by that matrix, resulting in n+p data blocks, which
you then write to your disks. When p disks failed, you erase from your
matrix the lines that correspond to the disks that failed, and invert
the resulting n*n matrix. Multiplying the n disks you do have by that
matrix result in the origin n data blocks.

The obvious first requirement from your erasure code matrix, therefor,
is that it be inversible after deleting any combination of p lines from
it. This is the property I'm trying to verify in my project at hand.

The usual erasure code matrix is calculated over ze ozer finite field,
i.e. Galois field. Frankly, I don't feel I understand Galois field, and
in particular, the way it is used in this particular case, enough to
explain why. One of the properties that make it attractive, however, is
that addition over GF is XOR. As a result, almost all RAID erasure code
matrices have their first n+1 lines look like this:

1 0 0 0 
0 1 0 0 
0 0 1 0 
0 0 0 1 
1 0 0
0 1 0
0 0 1
1 1 1 ... 1 1

The practical upshot of the above is that the first n disks receive the
same data they would have received without applying erasure coding (i.e.
- if they are available, they can be read directly without going through
the matrix, and more importantly, without reading the rest of the disks
in the stripe). Furthermore, the first protection disk contains the XOR
of all data disks in the stripe. In other words, if we lost only one
disk, we can employ RAID-5 as usual.

A side effect of the above is that the matrix is extremely sparse.
Almost all lines (all but the protection disks) contain just one
non-zero number, already on the diagonal.

Using Z2 instead of GF gives certain performance benefits. It does have
the cost of making the matrix much much much larger (hence the somewhat
insane numbers quoted in my original mail. I am not really building a
stripe of 272+12). Since the matrix is still extremely sparse, however,
this does not cost the full n^3 quoted by Matan.

Look up evenodd for an example of an algorithm that is based on XOR
rather than GF. It is not phrased in matrix form, but that is just a
convenience.

Hope this gives enough of an insight to quelch your curiosity :-)

Shachar
___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Shachar Shemesh]

On 10/08/15 17:32, Matan Ziv-Av wrote:

 At the end of this message is a python program with simple
 implementations of both algorithms (Gauss eliminiation and recursive).
 Run them for sizes 10 to 16 consecuitively to see how the difference
 between exponential and polynomial is very significant in this case.
1. Ask for help finding tools on mailing list
2. Get Oleg to question the viability of the suggested solution
3. Matan writes the tool you need for you
4. 
5. Profit


 The optimizations you suggested are possible (for both algorithms),
 but they are all just scaling the time needed. Even if you speed up by
 a factor of 10^9, the recursive algorithm will just not work.
I have not delved too deeply into the det calculation, but wouldn't
caching of sub-results cause an actual decrease in the complexity of the
run?

I've had a program I wrote once (for solving Nonograms
(https://en.wikipedia.org/wiki/Nonogram)) where adding caching of
intermediate results caused an complexity reduction. A riddle previously
solved in ~40 minutes was, after introducing caching, solved in 150
millisconds!!!

I even considered doing a Haifux lecture titled Complexity; why
programmers ignore it, and why it still matters.

Shachar
___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Oleg Goldshmidt]

Matan Ziv-Av ma...@svgalib.org writes:

 Please read what you reply to.

I assure you I read and understood Omer's and your posts. If you go back
to my reply you will surely realize that at no point I contradicted
you. I just pointed out that you didn't need to divide (by det(A)==1),
which would lead to the problem you correctly point out.

 The suggestion was to treat the matrix as a real matrix, so the
 calculations will not be modulo 2.

 If you take the, for example, matrix
 [ [  0,  0,  1,  1 ],
   [  0,  1,  0,  1 ],
   [  1,  0,  0,  1 ],
   [  1,  1,  1,  0 ] ]

 The inverse, in floating point numbers, will be something like
 [ [ -0.1, -0.1, 0.3,
 0.1 ],
   [ -0.1, 0.3, -0.1,
 0.1 ],
   [ 0.3, -0.1, -0.1,
 0.1 ],
   [ 0.1, 0.1, 0.1,
 -0.1 ] ]

To get that result you divided (by the determinant). All I said was you
did not need to. Apply mod 2 to all the (integer[*]) addition results,
and your determinant will be 1 (over Z2) and not 3.

Friends again? ;-)

[*] I strongly suspect you read too much into Omer's use of the word
real (also used in the OP).

-- 
Oleg Goldshmidt | p...@goldshmidt.org

___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Oleg Goldshmidt]

Matan Ziv-Av ma...@svgalib.org writes:

 The last line is wrong.

You are right.

 The naive algorithm, taught to any engineering or science student in
 the first linear algebra course, is Gauss elimination (also known as
 LU decomposition in this context). It runs in O(n^3) steps.

 Note that this algorithm is used very similarly for both inverting a
 matrix and calculating the determinant. So even if we replace step [5]
 in your suggestion, with Gaussian elimination, we still get O(n^5),
 when our code actually has all necessary components for running in
 O(n^3) instead.

A general comment. Asymptotic complexity has its uses but is very rarely
relevant in practice. One would probaly need a serious literature search
just to find out on what scale asymptotic complexity becomes relevant
for a given type of problem, and I will not be surprised if such a
search gives no generic result, or no practically useful result. In
practice, people keep solving problems that would require Hubble times
asymptotically.

There was no scale (or speed) requirement mentioned in the OP. Later,
Shachar mentioned 273x273 as a target. [He also said it was likely to be
sparse, so I wouldn't get stuck on O() estimates.] I admit I have not
done much matrix manipulation for quite a while, but 273x273 seems quite
large for a regular computer. It is not clear to me (I'll appreciate a
comment just for curiousity's sake as well as for education) that a
straightforward algorithm will be practical. Maybe one needs to think of
a highly paralellized algo on such scales. A CUDA (GPGPU, MIC, whatever)
computer may help, may or may not require custom implementation, and may
or may not make any differences in asymptotic complexity go away on the
300x300 scale.

On top of that, it is not clear to me how much the fact that + is XOR
and * is AND over Z2 may help (with or withut CUDA or similar).

-- 
Oleg Goldshmidt | p...@goldshmidt.org

___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Shachar Shemesh]

On 10/08/15 09:23, Oleg Goldshmidt wrote:
 A general comment. Asymptotic complexity has its uses but is very rarely
 relevant in practice. One would probaly need a serious literature search
 just to find out on what scale asymptotic complexity becomes relevant
 for a given type of problem, and I will not be surprised if such a
 search gives no generic result, or no practically useful result. In
 practice, people keep solving problems that would require Hubble times
 asymptotically.

 There was no scale (or speed) requirement mentioned in the OP. Later,
 Shachar mentioned 273x273 as a target. [He also said it was likely to be
 sparse, so I wouldn't get stuck on O() estimates.] I admit I have not
 done much matrix manipulation for quite a while, but 273x273 seems quite
 large for a regular computer.
74,000 cells hardly seem beyond the realm of recent[1] computer's power
to crunch. Even assuming straight on n^3, this means handling 20 million
cells. Do it in a non-compiled language, and it might take you a full
second (that's 100 cycles just to perform a single XOR).
  It is not clear to me (I'll appreciate a
 comment just for curiousity's sake as well as for education) that a
 straightforward algorithm will be practical.
As I've said before, I've inversed, using Gaussian elimination, a 20x20
(400 cells) matrix using nothing more than vi. I'll add that the bigger
the matrix, the sparser it is (all lines except 12, regardless of matrix
size, are already diagonal). Even had that not been the case, however, I
fail to see how these are matrix sizes beyond the reach of normal
computer's capabilities.

Shachar
1 - say, state of the art circa 2000.
___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Matan Ziv-Av]

On Sun, 9 Aug 2015, Oleg Goldshmidt wrote:


Matan Ziv-Av ma...@svgalib.org writes:


On Sat, 8 Aug 2015, Omer Zak wrote:


What happens if you use the regular matrix inversion tool which works
on real numbers?  (after rejecting, as singular over Z2, matrices
whose determinant modulo 2 is different from 1)


This will work if the inverse only has integer entries. It may also
work if your algorithm returns rational numbers, but will not work
with floating point numbers (there are no reals in a computer). You
cannot faithfully convert 1.1234 to an element of Z_2.


The original matrix contains zeros and ones, and you never need to
divide, just multiply and add modulo 2.


Please read what you reply to. The suggestion was to treat the matrix as 
a real matrix, so the calculations will not be modulo 2.


If you take the, for example, matrix
[ [  0,  0,  1,  1 ],
  [  0,  1,  0,  1 ],
  [  1,  0,  0,  1 ],
  [  1,  1,  1,  0 ] ]

The inverse, in floating point numbers, will be something like
[ [  -0.1,  -0.1,   0.3,   
0.1 ],
  [  -0.1,   0.3,  -0.1,   
0.1 ],
  [   0.3,  -0.1,  -0.1,   
0.1 ],
  [   0.1,   0.1,   0.1,  
-0.1 ] ]

And you have no idea if 0.3 should be 0 or 1 mod 2.

If you use rational numbers you get
[ [  -1/3,  -1/3,   2/3,   1/3 ],
  [  -1/3,   2/3,  -1/3,   1/3 ],
  [   2/3,  -1/3,  -1/3,   1/3 ],
  [   1/3,   1/3,   1/3,  -1/3 ] ]
Which is easy to convert (you ignore the denominators, which will all be 
odd for an invertible matrix).



--
Matan.


___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Matan Ziv-Av]

On Sun, 9 Aug 2015, Oleg Goldshmidt wrote:


Shachar Shemesh shac...@shemesh.biz writes:


Hi all,

I'm looking for a tool/code to invert a matrix. So far, this sounds
trivial. I have one special requirement. I did not think it was too
special, except I could not find anywhere that supplied it.

I want the matrix to be over a different field (i.e. - not the real
numbers). In my particular case, I want it to be over Z2 (zero and
one).


If you don't find ready code writing your own should be pretty
simple for Z2 - fields don't get any simpler. ;-)

In general, if you have a matrix A, then its inverse is given by

A^(-1) = adj(A)/det(A)   [1]

The determinant of any matrix over Z2 is either 0 or 1. If it is 0 the
matrix is not invertible. If it is 1, then the inverse matrix is the
same as the adjugate of the original matrix.

Now, the adjugate is the transpose of the cofactor matrix, which is

C_ij = (-1)^(i+j)*M_ij[2]

where M_ij is A's (ij)-minor, i.e., the determinant of the matrix
derived by deleting the i-th row and the j-th column of A. Thus

adj(A) = C_ji = (-1)^(i+j)*M_ji   [3]

Thus, from equations 1 and 3 we have

{A^(-1)}_ij = (-1)^(i+j)*M_ji [4]

There are probably library routines to compute minors and cofactors. If
you don't find any, then, given that all you have is zeroes and ones, it
should be easy and safe to write your own. Note that you need to compute
the determinant to determine whether or not your matrix is invertible,
and to compute the determinant you need the cofactors, since

det(A) = Sum_{i=1}^{n} (A_ij*C_ij)   [5]

So, compute det(A), keep the cofactors, transpose (Eq. [3]) - done. Use


The last line is wrong. The previous are mathematically correct, but 
computationally wrong.


When we compute det(A) using [5], we only calculate the minors for the 
first line, so we only know the minors for the first line, we still need 
to calculate them for the rest of the lines.


The calculation as suggested above will run in O(n!) steps, this will 
obviously stop working for matrices of size 15x15 or there about.


The naive algorithm, taught to any engineering or science student in the 
first linear algebra course, is Gauss elimination (also known as LU 
decomposition in this context). It runs in O(n^3) steps.


Note that this algorithm is used very similarly for both inverting a 
matrix and calculating the determinant. So even if we replace step [5] 
in your suggestion, with Gaussian elimination, we still get O(n^5), when 
our code actually has all necessary components for running in O(n^3) 
instead.


This is why when teaching about the classical adjoint forumula for 
inverse ([1]), or equivalently, the Cramer's rule for solving linear 
equations, it is very important to impress upon the students that while 
it appears simpler than Gauss elimination, it is in fact a lot less 
efficient.


As a side note, the best current algorithm runs in O(n^2.3727) (at least 
according to wikipedia), so if you care a lot about performance, you can 
still save some computation time by doing more research.



--
Matan.


___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Oleg Goldshmidt]

Shachar Shemesh shac...@shemesh.biz writes:

 Hi all,

 I'm looking for a tool/code to invert a matrix. So far, this sounds
 trivial. I have one special requirement. I did not think it was too
 special, except I could not find anywhere that supplied it.

 I want the matrix to be over a different field (i.e. - not the real
 numbers). In my particular case, I want it to be over Z2 (zero and
 one).

If you don't find ready code writing your own should be pretty
simple for Z2 - fields don't get any simpler. ;-)

In general, if you have a matrix A, then its inverse is given by

A^(-1) = adj(A)/det(A)   [1]

The determinant of any matrix over Z2 is either 0 or 1. If it is 0 the
matrix is not invertible. If it is 1, then the inverse matrix is the
same as the adjugate of the original matrix.

Now, the adjugate is the transpose of the cofactor matrix, which is

C_ij = (-1)^(i+j)*M_ij[2]

where M_ij is A's (ij)-minor, i.e., the determinant of the matrix
derived by deleting the i-th row and the j-th column of A. Thus

adj(A) = C_ji = (-1)^(i+j)*M_ji   [3]

Thus, from equations 1 and 3 we have

{A^(-1)}_ij = (-1)^(i+j)*M_ji [4]

There are probably library routines to compute minors and cofactors. If
you don't find any, then, given that all you have is zeroes and ones, it
should be easy and safe to write your own. Note that you need to compute
the determinant to determine whether or not your matrix is invertible,
and to compute the determinant you need the cofactors, since

det(A) = Sum_{i=1}^{n} (A_ij*C_ij)   [5]

So, compute det(A), keep the cofactors, transpose (Eq. [3]) - done. Use
normal integer arithmetic and take into account that over Z2 all odd
numbers are 1 and all even numbers are 0 (i.e., get the integer result
modulo 2). If you can overload + and * operators for type Z2 you can
make it pretty simple. And efficient, if you implement addition as XOR
and multiplication - as AND.

If you find, e.g., a decent templatized C++ inversion routine maybe you
can use it as is after overloading + and *?

Hope it helps,

-- 
Oleg Goldshmidt | p...@goldshmidt.org

___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Matan Ziv-Av]

On Sun, 9 Aug 2015, Shachar Shemesh wrote:


I should point out that the simplified matrix I was using to prove to myself 
that the idea has merit is 20x20 (inversed using state of the art in the vi 
text editing front). The code
I'll actually have to run will be 273x273. The Matrix itself is sparsish, so 
it's really not that bad. Still, to prove things are working I'll have to 
(probably pre-calculate) several
thousand such matrices.

In fact, one of my problems in using tools such as Mathematica and friends is 
that I don't want to hand code the Matrix to be inversed.


GAP (and similarly SAGE, maxima) can be scripted.

You do not give your exact setup, but if you can write the matrices to a 
text file in any format, you can read it in GAP. If you can output to 
the same format as I posted, you do not even need to write any program 
in GAP to read it.




--
Matan.


___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Matan Ziv-Av]

On Sun, 9 Aug 2015, Shachar Shemesh wrote:

I should point out that the simplified matrix I was using to prove to 
myself that the idea has merit is 20x20 (inversed using state of the 
art in the vi text editing front). The code I'll actually have to run 
will be 273x273. The Matrix itself is sparsish, so it's really not 
that bad. Still, to prove things are working I'll have to (probably 
pre-calculate) several thousand such matrices.


Actually, for this specific problem, implementing Gaussian elimination 
is much better than looking for a library or a tool, and interfacing 
with it.


Untested C-Pseudo code:

Input: A,B: nxn matrices, B=I_n
Output: det(A), B=A^{-1} if A det=1

for(i=0;in;i++) {
  for(j=i;jn;j++) if(A[j][i]==1) {
ExchangeLines(A,i,j);
ExchangeLines(B,i,j);
break;
  }
  if(j==n) return 0;
  for(k=1;kn;k++) if(A[k][i]==1  k!=j) {
AddLines(A,k,j);
AddLines(B,k,j);
  }
}
return 1;




--
Matan.


___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Evgeniy Ginzburg]

On Aug 9, 2015 20:15, Matan Ziv-Av ma...@svgalib.org wrote:

 On Sun, 9 Aug 2015, Shachar Shemesh wrote:

 I should point out that the simplified matrix I was using to prove to
myself that the idea has merit is 20x20 (inversed using state of the art in
the vi text editing front). The code
 I'll actually have to run will be 273x273. The Matrix itself is
sparsish, so it's really not that bad. Still, to prove things are working
I'll have to (probably pre-calculate) several
 thousand such matrices.

 In fact, one of my problems in using tools such as Mathematica and
friends is that I don't want to hand code the Matrix to be inversed.


 GAP (and similarly SAGE, maxima) can be scripted.

 You do not give your exact setup, but if you can write the matrices to a
text file in any format, you can read it in GAP. If you can output to the
same format as I posted, you do not even need to write any program in GAP
to read it.

Not being connected to the field of applied mathematics can only  recommend
solutions observed.
There is vast amount of code already written for LinAlg.
in python you can use numpy.
In C(++) any BLAS library have all you need.
OpenBLAS seems more effective.
If yo need to manipulate matrices en masse strongly suggested to use GPU.
Both OpenCL and CUDA are good.

Best Regards, Evgeniy.
___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Omer Zak]

What happens if you use the regular matrix inversion tool which works on
real numbers?
(after rejecting, as singular over Z2, matrices whose determinant modulo
2 is different from 1)


On Sat, 2015-08-08 at 20:31 +0300, Shachar Shemesh wrote:
 Hi all,
 
 I'm looking for a tool/code to invert a matrix. So far, this sounds
 trivial. I have one special requirement. I did not think it was too
 special, except I could not find anywhere that supplied it.
 
 I want the matrix to be over a different field (i.e. - not the real
 numbers). In my particular case, I want it to be over Z2 (zero and
 one).
 
 So far, I have failed to find such a tool. If anyone knows how to do
 it, please let me know, as the alternative is writing one myself,
 which is something I REALLY don't want to do without a good reason.

-- 
If verbal consent is not obtained in triplicate, it is a date rape.
Asking permission constitutes harassment.

My opinions, as expressed in this E-mail message, are mine alone.
They do not represent the official policy of any organization with which
I may be affiliated in any way.
WARNING TO SPAMMERS:  at http://www.zak.co.il/spamwarning.htmlDelay is the 
deadliest form of denial.C. Northcote Parkinson
My own blog is at http://www.zak.co.il/tddpirate/

My opinions, as expressed in this E-mail message, are mine alone.
They do not represent the official policy of any organization with which
I may be affiliated in any way.
WARNING TO SPAMMERS:  at http://www.zak.co.il/spamwarning.html


___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Matan Ziv-Av]

On Sat, 8 Aug 2015, Omer Zak wrote:


What happens if you use the regular matrix inversion tool which works on
real numbers?
(after rejecting, as singular over Z2, matrices whose determinant modulo
2 is different from 1)


This will work if the inverse only has integer entries. It may also work 
if your algorithm returns rational numbers, but will not work with 
floating point numbers (there are no reals in a computer). You cannot 
faithfully convert 1.1234 to an element of Z_2.



On Sat, 2015-08-08 at 20:31 +0300, Shachar Shemesh wrote:

Hi all,

I'm looking for a tool/code to invert a matrix. So far, this sounds
trivial. I have one special requirement. I did not think it was too
special, except I could not find anywhere that supplied it.

I want the matrix to be over a different field (i.e. - not the real
numbers). In my particular case, I want it to be over Z2 (zero and
one).

So far, I have failed to find such a tool. If anyone knows how to do
it, please let me know, as the alternative is writing one myself,
which is something I REALLY don't want to do without a good reason.


You can use GAP ( http://www.gap-system.org/ ).





--
Matan.


___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Yaacov Weiss]

On Sat, Aug 8, 2015 at 8:31 PM, Shachar Shemesh shac...@shemesh.biz wrote:

 I want the matrix to be over a different field (i.e. - not the real
 numbers). In my particular case, I want it to be over Z2 (zero and one).

The top results of a search for Finite Field library look promising.

___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Shachar Shemesh]

 

On 08/08/2015 21:31, Yaacov Weiss wrote: 

 On Sat, Aug 8, 2015 at 8:31 PM, Shachar Shemesh shac...@shemesh.biz wrote:
 
 I want the matrix to be over a different field (i.e. - not the real 
 numbers). In my particular case, I want it to be over Z2 (zero and one).
 
 The top results of a search for Finite Field library look promising.

Yes, Givaro seems promising. 

I did not try this search because most results are for Galois fields
(which, granted, are not that different for the specific case of 2,
but still). I'll have a look into that. I might eventually need to bind
to it from D, which will probably not be fun, but we'll cross that
bridge when its time comes. 

Many people sent suggestions in private. I'll point out that: 

* I tried using Boost's matrix code with a type that is a special
class I wrote. Not only did it not work, I couldn't even decipher what
it was that it was missing in order to get it to work. The error
messages were 300 characters long and five to six lines long PER ERROR.
Even when unravelled, they complain that some internal class used by
Boost is not comparable (or something) to some other internal class used
by Boost.
* My linear algebra isn't as well remembered as I thought it was. When
I manually inverse a matrix, I use row replacement, addition and
subtraction. I vaguely remember what covariants are, and no recollection
at all of adj. I will definitely look them up before I continue, but
it's somewhat sad when things you once knew you no longer do.

Unrelated to the above, but does anyone have a GOOD source explaining
Galois fields? Everything I found so far left me confused about whether
it is used directly (i.e. - numbers treated as polynoms, divided by a
modulus), or via a generator. Also, I know they are used for Raid-6
calculations, but it seems to me that if I multiply a value by 2, I am
going to get an overflow (unless I'm modulus something which isn't even,
in which case I cannot represent all 2^32 values of an int). If anyone
has any source that clears up that confusion for me, please send me a
link. 

Thanks, 

Shachar 
 ___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il

Re: Matrix inversion tool

[Oleg Goldshmidt]

Matan Ziv-Av ma...@svgalib.org writes:

 On Sat, 8 Aug 2015, Omer Zak wrote:

 What happens if you use the regular matrix inversion tool which works
 on real numbers?  (after rejecting, as singular over Z2, matrices
 whose determinant modulo 2 is different from 1)

 This will work if the inverse only has integer entries. It may also
 work if your algorithm returns rational numbers, but will not work
 with floating point numbers (there are no reals in a computer). You
 cannot faithfully convert 1.1234 to an element of Z_2.

The original matrix contains zeros and ones, and you never need to
divide, just multiply and add modulo 2. 

-- 
Oleg Goldshmidt | p...@goldshmidt.org

___
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il