I cannot work out from these references whether you regard multimodular or p-adic as the way to go. 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 > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
