Hi there, the discussion below started off-list but we figured it should be on [sage-devel] instead. I left out a few e-mails from people who didn't explicitly agree to have their e-mails on [sage-devel].
-------------------------------------------- Daniel: > > Yes, sparse LA is definitely the main obstacle and yes I'm trying to > > implement it myself. I know of the existence of M4RI but I'm interested > > in larger fields and also in large systems that require sparse LA. > > My approach has been to use Markowitz Pivoting, since this seems to be > > what they use in Magma. > > Out of curiosity: how did you come to this conclusion? This is not really clear to me, but here are 2 sources that make me think so: 1. In Sparse matrix kernel function Magma Handbook: "The algorithm first performs sparse elimination using Markowitz pivoting ([DEJ84, Sec. 9.2]) to obtain a smaller dense matrix, then the nullspace algorithm for dense-representation matrices is applied to this matrix." And in some other algorithms for sparse matrices it mentions Markowitz pivoting. 2. in the F4 paper: "In the current implementation of the algorithm we use by default the structured Gaussian elimination. Note that in an ideal implementation the program should first analysed the shape of the matrix and then decided which algorithm should be applied." And we know that Structured gaussian elimination is just an adaptation of the Markowitz pivoting strategy. > > I believe that my implementation of the basic Gaussian > > elimination using Markowitz Pivoting is comparable to Magma's. > How do you measure this? As far as I know Magma does not expose its sparse > linear algebra to the end user. You are right, but Magma has a sparse matrix type and related algorithms, so I compare to those. Say, I compare Magma's Rank procedure for sparse matrices, with my own Markowitz Pivoting gaussian elimination. > > But the > > problem is that the Markowitz Pivoting doesn't respect the order of the > > columns so we need to adapt the algorithm for F4. I've tried all kinds > > for adaptations, but nothing seems to be good enough. > You mean 'good enough' in terms of performance? I compare matrix reduction time, sparsity before and after reduction, matrix sizes. > What examples/ideals are you optimising for and what are the times you get > for those? I've tested some ideals that come from cryptography, specifically some from MPKCs over GF(2^8) and also random sets of generators with similar characteristics. The times are between 10 and 100 times higher than Magma in terms of matrix reduction time. > Also, do you cross over to a dense implementation if the matrices get too > dense? Yes and not. At this point I don't change the data structure when it gets too dense, but I do switch to a dense algorithm. I don't really know if a dense representation would make a big difference. Also I don't know exactly at what level of density it would. > > If this makes sense to anybody else, I'd like to discuss how to overcome > > this obstacle. > > I was toying with the idea to have a hybrid implementation where left-most > columns are sparse and the right-most columns are dense. It seems the > matrices which arise during F4 and friends usually follow this pattern. Do you use different data structures? how do you choose pivots? How do you decide where to split? Do you keep the separation static or do you change it along the way? > Cheers, > Martin > > PS: It seems this discussion should happen on [sage-devel] where more > people interested in the matter can jump in if they want to. I guess so. Feel free to publish it. Cheers, Daniel --------------------------------------------------------------- Hi, Yes, sparse LA is definitely the main obstacle and yes I'm trying to implement it myself. I know of the existence of M4RI but I'm interested in larger fields and also in large systems that require sparse LA. My approach has been to use Markowitz Pivoting, since this seems to be what they use in Magma. I believe that my implementation of the basic Gaussian elimination using Markowitz Pivoting is comparable to Magma's. But the problem is that the Markowitz Pivoting doesn't respect the order of the columns so we need to adapt the algorithm for F4. I've tried all kinds for adaptations, but nothing seems to be good enough. If this makes sense to anybody else, I'd like to discuss how to overcome this obstacle. Thanks for the quick reply Martin. Daniel Cabarcas > Hi there, > > I think Ralf-Phillip Weinmann so far came closest to have an implementation > which has acceptable performance over several base fields. > > In the boolean polynomial ring > > F_2[x_1,...x,_n]/<x_1^2 + x_1, ..., x_n^2 + x_n> > > PolyBoRi has an implementation of F4: It implements SlimGB and also > supports the option 'faugere=True' which uses the M4RI dense linear algebra > library to perform the top-reductions: thus, F4. > > Did you implement the linear algebra yourself? I guess good sparse LA is > one of the main obstacles. > > Martin ------------------------------------------------------------------- On Sun, Apr 26, 2009 at 5:49 PM, Daniel Cabarcas wrote: > Dear Dr. Stein, > > Is there somebody in the SAGE project currently working on the > implementation of F4. If so, I'd like to get in contact to share ideas. > There are several people who have tried to implement an F4 for Sage. Thus foar, nobody seem to have really pushed this to the point that it is better in (many?) cases than the non-F4 Groebner basis algorithm in Singular. > I'm a math PhD student at the University of Cincinnati under the advise of > Jintai Ding. I've been working independently on an implementation of F4 with > moderate success. Since we share similar goals I thought We might be able to > help each other. Cool! I've cc'd this message to all the other people I know of involved with Sage who have worked on F4. William -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://www.informatik.uni-bremen.de/~malb _jab: martinralbre...@jabber.ccc.de --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
