On Sun, Feb 1, 2009 at 11:21 AM, Roman Pearce <[email protected]> wrote: > > I just want to point out the Maple's linear algebra is not quite as > bad as old Linbox times imply. The linalg package has been obsolete > for some time now.
It should print a deprecation warning so I would know. Could you suggest that? Does A := LinearAlgebra:-RandomMatrix(n); create a random matrix with entries uniformly distributed between -99 and 99? I just tried a few timings comparing Sage and Maple with the commands you suggest and using "a = random_matrix(ZZ,200,x=-99,y=99)" in Sage: n=200, sage: 0.56 n=200, Maple: 0.52 n=400, sage: 3.22 seconds n=400, maple: 6.07 seconds n=800, sage: 25.1 seconds n=800, maple: 146.4 seconds n=1200, sage: 83.3 seconds n=1200, maple: Thanks for pointing out that I wasn't using the optimal command in Maple. I had found those commands by searching the web and doing what the web pages I found suggested. Obviously, that's not the right way to use Maple. What algorithm is maple using to compute the determinants of integer matrices? I'm curious if it is the same one as Sage uses, but Maple is just slower because of a worse implementation. Based on the timing discrepancies above, though, it appears that Maple is using a much much worse O complexity algorithm. Also, how does Maple behave if the input involves very large numbers? For example, in Sage for 129-bit input: sage: a = random_matrix(ZZ,200,x=-2^128,y=2^128) sage: time d = a.det() CPU times: user 4.48 s, sys: 0.00 s, total: 4.48 s and for 513-bit input: sage: a = random_matrix(ZZ,200,x=-2^512,y=2^512) sage: time d = a.det() CPU times: user 73.76 s, sys: 0.01 s, total: 73.77 s By the way, most of the work for Sage computing dets uses IML, not Linbox. Linbox is only used at the very end to compute a couple of determinants mod p. I think Linbox has a det algorithm, but there is a subtle overflow issue involving computing the Hadamard bound when the input matrix has huge entries, which requires using either MPFR (with Linbox doesn't depend on) or some tedious-to-implement algorithm which never got implemented in Linbox.... Also, IML is faster/more robust at solving A*x = b than Linbox, I think, so IML's det may suffer from that. On the other hand, for all I know Clement fixed all these issues in Linbox, and they aren't a problem anymore. -- William > > -bash-3.2$ maple > |\^/| Maple 12 (X86 64 LINUX) > ._|\| |/|_. Copyright (c) Maplesoft, a division of Waterloo Maple > Inc. 2008 > \ MAPLE / All rights reserved. Maple is a trademark of > <____ ____> Waterloo Maple Inc. > | Type ? for help. >> A := LinearAlgebra:-RandomMatrix(200); > [ 200 x 200 > Matrix ] > A := [ Data Type: > anything ] > [ Storage: > rectangular ] > [ Order: > Fortran_order ] > >> time(LinearAlgebra:-Determinant(A)); > 0.479 > >> A := matrix(convert(A,listlist)): >> time(linalg[det](A)); > 19.699 > > > The next release of Maple should have similar improvements for solving > dense linear systems. It's not as fast as LinBox, but it's not > embarrassing :) > > > -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] 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 -~----------~----~----~----~------~----~------~--~---
