2008/4/28 William Stein <[EMAIL PROTECTED]>: > > On Mon, Apr 28, 2008 at 12:54 AM, John Cremona <[EMAIL PROTECTED]> wrote: > > > > I cannot work out from these references whether you regard > > multimodular or p-adic as the way to go. > > For practical linear algebra -- i.e., where you care about how fast > algorithms actually run rather than only caring about theoretical > big-Oh complexity -- it is critically important to implement both > multimodular and p-adic algorithms. For example, when computing > the reduced echelon form of an n x m matrix, which algorithm to > use depends a lot on: > 1) the relative size of n and m. > 2) the size of the entries of the input matrix > 3) the expected size of the output matrix > > For some algorithms, e.g., charpoly and matrix multiplication, multimodular > is always the way to go. For others, e.g., solving A*x = b for b a vector, > p-adic is the right choice in the vast majority of cases. >
Thanks, that's a very useful and helpful answer! John > > > > Or are you intending to try > > both and compare them? > > > > John > > > > 2008/4/28 William Stein <[EMAIL PROTECTED]>: > > > > > > > > > > Hi, > > > > > > Regarding fast cyclotomic linear algebra, there is now a wiki page up: > > > > > > http://wiki.sagemath.org/cyclo > > > > > > which has a link to some code, todo list, notes, etc., We > > > have a basic matrix type for cyclotomic > > > linear algebra, and today Craig and I worked on fast multimodular > charpoly. > > > Our first implementation of that is "one hundred times" faster than > > > Magma/PARI/Sage/etc., for a specific example of a 132x132 matrix > > > over CyclotomicField(11) that comes up when computing modular > > > forms with nontrivial character. > > > > > > -- William > > > > > > > > > > > > > > > > > > On Sat, Apr 26, 2008 at 12:31 PM, William Stein <[EMAIL PROTECTED]> > wrote: > > > > On Fri, Apr 25, 2008 at 7:10 PM, Kiran Kedlaya <[EMAIL PROTECTED]> > wrote: > > > > > > > > > > Is the strategy to work multimodularly using completely split > primes? > > > > > Or does someone have a better idea? > > > > > > > > > > > > > Here's an IRC chat: > > > > > > > > 12:17 < wstein> btw, I thought a bit about cyclotomic linear > algebra. > > > > 12:17 < craigcitro> so do you have a game plan for the linear > algebra > > > > over cyclotomic fields? > > > > 12:17 < wstein> One basically problem is solving A*X = B. > > > > 12:17 < craigcitro> haha we typed that at exactly the same time > > > > 12:17 < wstein> One can reduce a lot of things to this, including > some > > > > cases of echelon form. > > > > 12:17 < wstein> :-) > > > > 12:17 < wstein> I thought of and implemented a toy version of a > p-adic > > > > algorithm to solve the above. > > > > 12:18 < wstein> Here's the idea. > > > > 12:18 < craigcitro> k > > > > 12:18 < wstein> 1. Choose a prime p that splits completely in > Q(zeta_n). > > > > 12:18 < wstein> 2. Using that prime, view A as a matrix with > entries in Q_p. > > > > 12:18 < wstein> 3. Using Dixon p-adic lifting solve A_p * X = B_p > > > > p-adically to some precision. > > > > 12:18 -!- Roed [EMAIL PROTECTED] has joined #sage-devel > > > > 12:19 < wstein> I think 3 can be done by hacking on the IML source > code some. > > > > 12:19 -!- Roed [EMAIL PROTECTED] has quit [Client Quit] > > > > 12:19 < craigcitro> cool. i haven't looked at IML at all ... > > > > 12:19 < wstein> 4. Using LLL go from a p-adic solution to A_p * X_p > = > > > > B_p to a rational solution > > > > 12:19 < wstein> to A*X = B. > > > > 12:19 < wstein> All of the above definitely works. > > > > 12:19 < wstein> The question is making it fast. > > > > 12:19 < craigcitro> nod > > > > 12:19 < wstein> It took me a little while to remember how to use > LLL for step 4. > > > > 12:20 < wstein> But all you do is embed the powers of zeta_n in Q_p. > > > > 12:20 < wstein> Then you make a matrix that is basically the > identity > > > > matrix with the powers of zeta_n > > > > 12:20 < wstein> reduced mod p^m as the last column. > > > > 12:20 < wstein> Finally the very bottom-right entry is an entry of > X_p. > > > > 12:20 < wstein> Then you LLL reduce that matrix, and from the result > > > > 12:21 < wstein> you can read of the best element of Q(zeta_n) that > > > > approximates that element of X_p, > > > > 12:21 < wstein> with high probability. > > > > 12:21 < wstein> At the end you double-check the answer, if > proof=True. > > > > 12:21 < wstein> So we will also need fast matrix multiplication, > which > > > > is just CRT. > > > > 12:21 < wstein> (and doing it over a finite field) > > > > 12:21 < wstein> Using Clements FFLASS. > > > > 12:22 < wstein> There is also an obvious multimodular echelon > > > > algorithm, but I'm *not* convinced > > > > 12:22 < wstein> it is a good idea. > > > > 12:22 < craigcitro> hm > > > > 12:22 < wstein> Often p-adic algorithms are a bit better -especially > > > > in practice- than multimodular algorithms. > > > > 12:22 < robertwb> the p-adic method beats out multimodular for QQ, > right? > > > > 12:22 < wstein> In a lot of cases, yes. > > > > 12:22 < robertwb> (for echelon) > > > > 12:23 < wstein> The issue is that the answers are *huge*, so with > > > > multimodular you have to > > > > 12:23 < wstein> work modulo a lot of primes. > > > > 12:23 < wstein> The shape of the matrix is also relevant. > > > > 12:24 < robertwb> and with padic lifting, the lifting p^n -> p^(n+1) > > > > is computationally easier than doing a new prime, right? > > > > 12:24 -!- Roed [EMAIL PROTECTED] has joined #sage-devel > > > > 12:24 < wstein> Yes, it's basically just one matrix vector multiply > over F_p. > > > > 12:24 -!- Roed [EMAIL PROTECTED] has quit [Client Quit] > > > > 12:24 < wstein> That's O(n^2). > > > > 12:24 < wstein> But echelon modulo a new prime is O(n^omega). > > > > > > > > > > > > -- > > > > > > > > Note also -- there is a masters thesis by somebody from SFU on > > > > cyclotomic linear algebra. > > > > > > > > William > > > > > > > > > > > > > > > > -- > > > > > > William Stein > > > Associate Professor of Mathematics > > > University of Washington > > > http://wstein.org > > > > > > > > > > > > > > > > > > > > > > > > > -- > William Stein > Associate Professor of Mathematics > University of Washington > http://wstein.org > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
