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