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 -~----------~----~----~----~------~----~------~--~---
