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