On Wednesday 12 November 2008, Michel wrote: > Ok that hint was not sufficient. > > What function(s) from the m4ri library would allow me to attack this > problem? > How do I express that the solution of the system is supposed to be > sparse > (which is a non-linear condition)? > As far as I can tell there is no real reference manual for m4ri. > > Regards, > Michel > > BTW I more or less know how this problem is attacked in characteristic > zero. > > On Nov 12, 11:10 am, Michael Brickenstein <[EMAIL PROTECTED]> wrote: > > http://m4ri.sagemath.org/performance.html > > > > On 12 Nov., 11:07, Michel <[EMAIL PROTECTED]> wrote: > > > > If the equations are really linear, then it's trivial. > > > > > > Ah, can you tell me more? > > > > > > Regards, > > > Michel
Hi there, I am surprised that this question is addressed to me and not to [sage-devel] in general. If I understand correctly, you are not asking how to solve a system of linear equations (this is what Michael referred to M4RI for) but how to express the low hamming weight of the solution. I don't have an elegant solution. One way to express sparsity is to add say quadratic equations of the form x_i* x_j = 0 for random i and j with i != j to your equation system. However, this approach is very limited. Another approach: sage: A = random_matrix(GF(2),64,782) # 781 + constant coefficient sage: VS = A.right_kernel() # very slow due to silly reasons sage: M = VS.basis_matrix() #also slow due to silly reasons Now the problem is: Is there a linear combination of rows with hamming weight smaller than some threshold, right? This smells like a hard problem to me. You might get lucky though: sage: mx = M.ncols() sage: oldr = 0 sage: for r in range(M.nrows()): ... if sum(map(ZZ,M[r])) < mx: ... mx = sum(map(ZZ,M[r])) .... oldr = r sage: mx 18 Does this help? I suppose I'm only telling you things you already knew. PS: M4RI does have a reference manual. I think M4RI mainly lacks high-level documentation like a tutorial and such. -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _www: http://www.informatik.uni-bremen.de/~malb _jab: [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
