[sage-devel] problem with showing plots from command line
Hi folks. I tried to send the following email a few hours ago (but I put the email address in wrong) and I don't feel like rewriting it all. So I should add to it now that I have upgraded sage (so I am running 2.8.8.1) and the error still occurs. Perhaps I should open a ticket for this, but perhaps I should also wait to see it anyone else can duplicate this problem. - Hi all. I apologize for not upgrading to the latest version of sage before writing this email, but I didn't see any tickets about this on the since 2.8.7.2, so perhaps no one else has had this problem. (And I am upgrading now, but if I don't send this email now, I might forget about it for a few days). Anyway, the following takes place on a Intel Core Duo (not Core 2, so just 32 bits) newly upgraded to Ubuntu 7.10, and running sage 2.8.7.2. Briefly, plot().show() isn't working for me. After looking into the problem a little bit, I modified the code for show() so that it would print out the command line that it was using, along with any errors. I get the following: sage: f(x) = x*exp(-4*x) sage: P = f.plot() sage: P.show() xdg-open /home/bober/.sage//temp/bober/11314//tmp_0.png sage: eog: symbol lookup error: /usr/lib/libxml2.so.2: undefined symbol: gzopen64 So there is some sort of library problem. But if I execute the same command from a plain shell: [EMAIL PROTECTED]:~$ xdg-open /home/bober/.sage//temp/bober/11314//tmp_0.png eog opens the file just fine. So it seems that sage is somehow screwing up library search paths, or perhaps when eog is run from within sage it is trying to use some libraries that sage provides and some libraries that Ubuntu provides, and those libraries don't play nice together. Or something like that is going on. plot().show() also does not work anymore for me when running sage 2.8.2, and it certainly used to before I upgraded Ubuntu, so it is probably safe to assume that it is getting the same error, and that this error was caused by the upgrade. (I haven't actually taken the time to verify that eog gives the same library error when run from 2.8.2, however.) This is probably beyond my ability to debug any further without spending many hours, so hopefully someone knows how to fix this easily, or can at least point me in the right direction. --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: problem with showing plots from command line
On Oct 23, 8:20 am, Jonathan Bober [EMAIL PROTECTED] wrote: Hi folks. Hello Jonathan, I tried to send the following email a few hours ago (but I put the email address in wrong) and I don't feel like rewriting it all. So I should add to it now that I have upgraded sage (so I am running 2.8.8.1) and the error still occurs. Perhaps I should open a ticket for this, but perhaps I should also wait to see it anyone else can duplicate this problem. - Hi all. I apologize for not upgrading to the latest version of sage before writing this email, but I didn't see any tickets about this on the since 2.8.7.2, so perhaps no one else has had this problem. (And I am upgrading now, but if I don't send this email now, I might forget about it for a few days). Anyway, the following takes place on a Intel Core Duo (not Core 2, so just 32 bits) newly upgraded to Ubuntu 7.10, and running sage 2.8.7.2. Briefly, plot().show() isn't working for me. After looking into the problem a little bit, I modified the code for show() so that it would print out the command line that it was using, along with any errors. I get the following: sage: f(x) = x*exp(-4*x) sage: P = f.plot() sage: P.show() xdg-open /home/bober/.sage//temp/bober/11314//tmp_0.png sage: eog: symbol lookup error: /usr/lib/libxml2.so.2: undefined symbol: gzopen64 Could you give us the output from echo 'LD_LIBRARY_PATH' and 'ldd xdg- open' with and without sourcing sage-env. If you add an 'echo LD_LIBRARY_PATH' right before xdg-open is called in P.show() From the name of the symbol I would guess that it is a libz incompability. There was a patch to the launch code for firefox/ iceweasel that malb made because of a similar issue. Maybe we need to reset LD_LIBRARY_PATH to the old value before we modify it in sage-env in case we launch external helper applications. So there is some sort of library problem. But if I execute the same command from a plain shell: [EMAIL PROTECTED]:~$ xdg-open /home/bober/.sage//temp/bober/11314//tmp_0.png eog opens the file just fine. So it seems that sage is somehow screwing up library search paths, or perhaps when eog is run from within sage it is trying to use some libraries that sage provides and some libraries that Ubuntu provides, and those libraries don't play nice together. Or something like that is going on. plot().show() also does not work anymore for me when running sage 2.8.2, and it certainly used to before I upgraded Ubuntu, so it is probably safe to assume that it is getting the same error, and that this error was caused by the upgrade. (I haven't actually taken the time to verify that eog gives the same library error when run from 2.8.2, however.) This is probably beyond my ability to debug any further without spending many hours, so hopefully someone knows how to fix this easily, or can at least point me in the right direction. Cheers, Michael --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Unhandled SIGSEGV: Ticket #973
Last year after less than two days I could finish a calculation and write to William: Original Message Subject: dance(10) Date: Thu, 09 Mar 2006 00:10:19 +0100 From: Jaap Spies [EMAIL PROTECTED] To: William Stein [EMAIL PROTECTED] William, Some time ago, dance(10) finished: sage: time dance(10) [1, 90, 3405, 71040, 901152, 7225344, 36862960, 117340800, 221170456, 220658800, 87396728] h^10 - 35*h^9 + 675*h^8 - 8610*h^7 + 78435*h^6 - 523467*h^5 + 2562525*h^4 - 9008160*h^3 + 21623220*h^2 - 31840760*h + 21750840 CPU times: user 141822.70 s, sys: 18387.03 s, total: 160209.74 s Wall time: 165997.13 Jaap To day I got with sage-2.8.8.1: sage: time dance(10) Unhandled SIGSEGV: A segmentation fault occured in SAGE. This probably occured because a *compiled* component of SAGE has a bug in it (typically accessing invalid memory) or is not properly wrapped with _sig_on, _sig_off. You might want to run SAGE under gdb with 'sage -gdb' to debug this. SAGE will now terminate (sorry). With sage -gdb: sage: time dance(9) h^9 - 27*h^8 + 414*h^7 - 4158*h^6 + 29421*h^5 - 148743*h^4 + 530796*h^3 - 1276992*h^2 + 1866384*h - 1255608 CPU times: user 1786.82 s, sys: 23.05 s, total: 1809.87 s Wall time: 1831.52 sage: time dance(10) Program received signal SIGSEGV, Segmentation fault. [Switching to Thread -1208523072 (LWP 30162)] 0x0064d473 in strlen () from /lib/libc.so.6 (gdb) The program (see below) uses methods from sage.matrix.matrix2.pyx Jaap ## # Copyright (C) 2006 Jaap Spies, [EMAIL PROTECTED] # # Distributed under the terms of the GNU General Public License (GPL): # # http://www.gnu.org/licenses/ ## Usage from sage sage: attach 'dancing.sage' sage: dance(4) h^4 - 2*h^3 + 9*h^2 - 8*h + 6 # use variable 'h' in the polynomial ring over the rationals h = QQ['h'].gen() def dance(m): Generates the polynomial solutions of the Dancing School Problem Based on a modification of theorem 7.2.1 from Brualdi and Ryser, Combinatorial Matrix Theory. See NAW 5/7 nr. 4 december 2006 p. 285 INPUT: integer m OUTPUT: polynomial in 'h' EXAMPLE: sage: dance(4) h^4 - 2*h^3 + 9*h^2 - 8*h + 6 AUTHOR: Jaap Spies (2006) n = 2*m-2 M = MatrixSpace(ZZ, m, n) A = M([0 for i in range(m*n)]) for i in range(m): for j in range(n): if i j or j i + n - m: A[i,j] = 1 rv = A.rook_vector() # print rv s = sum([(-1)^k*rv[k]*falling_factorial(m+h-k, m-k) for k in range(m+1)]) print s --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: problem with showing plots from command line
On 10/23/07, Jonathan Bober [EMAIL PROTECTED] wrote: Hi folks. I tried to send the following email a few hours ago (but I put the email address in wrong) and I don't feel like rewriting it all. So I should add to it now that I have upgraded sage (so I am running 2.8.8.1) and the error still occurs. Perhaps I should open a ticket for this, but perhaps I should also wait to see it anyone else can duplicate this problem. - Hi all. I apologize for not upgrading to the latest version of sage before writing this email, but I didn't see any tickets about this on the since 2.8.7.2, so perhaps no one else has had this problem. (And I am upgrading now, but if I don't send this email now, I might forget about it for a few days). Anyway, the following takes place on a Intel Core Duo (not Core 2, so just 32 bits) newly upgraded to Ubuntu 7.10, and running sage 2.8.7.2. Briefly, plot().show() isn't working for me. After looking into the problem a little bit, I modified the code for show() so that it would print out the command line that it was using, along with any errors. I get the following: sage: f(x) = x*exp(-4*x) sage: P = f.plot() sage: P.show() xdg-open /home/bober/.sage//temp/bober/11314//tmp_0.png sage: eog: symbol lookup error: /usr/lib/libxml2.so.2: undefined symbol: gzopen64 This works for mebut it opens up gimp (ubuntu 64bit) and previewer (intel macbook) as the graphics viewer, instead of a separate tab of firefox which is what it did before. I actually prefer the new behaviour (it makes my workflow a bit more efficient), but agree with you that something seems to have changed. Out of curiosity, is gimp installed on your system? So there is some sort of library problem. But if I execute the same command from a plain shell: [EMAIL PROTECTED]:~$ xdg-open /home/bober/.sage//temp/bober/11314//tmp_0.png eog opens the file just fine. So it seems that sage is somehow screwing up library search paths, or perhaps when eog is run from within sage it is trying to use some libraries that sage provides and some libraries that Ubuntu provides, and those libraries don't play nice together. Or something like that is going on. plot().show() also does not work anymore for me when running sage 2.8.2, and it certainly used to before I upgraded Ubuntu, so it is probably safe to assume that it is getting the same error, and that this error was caused by the upgrade. (I haven't actually taken the time to verify that eog gives the same library error when run from 2.8.2, however.) This is probably beyond my ability to debug any further without spending many hours, so hopefully someone knows how to fix this easily, or can at least point me in the right direction. --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: Unhandled SIGSEGV: Ticket #973
On Oct 23, 1:23 pm, Jaap Spies [EMAIL PROTECTED] wrote: Last year after less than two days I could finish a calculation and write to William: Original Message Subject: dance(10) Date: Thu, 09 Mar 2006 00:10:19 +0100 From: Jaap Spies [EMAIL PROTECTED] To: William Stein [EMAIL PROTECTED] William, Some time ago, dance(10) finished: sage: time dance(10) [1, 90, 3405, 71040, 901152, 7225344, 36862960, 117340800, 221170456, 220658800, 87396728] h^10 - 35*h^9 + 675*h^8 - 8610*h^7 + 78435*h^6 - 523467*h^5 + 2562525*h^4 - 9008160*h^3 + 21623220*h^2 - 31840760*h + 21750840 CPU times: user 141822.70 s, sys: 18387.03 s, total: 160209.74 s Wall time: 165997.13 Jaap To day I got with sage-2.8.8.1: sage: time dance(10) Unhandled SIGSEGV: A segmentation fault occured in SAGE. This probably occured because a *compiled* component of SAGE has a bug in it (typically accessing invalid memory) or is not properly wrapped with _sig_on, _sig_off. You might want to run SAGE under gdb with 'sage -gdb' to debug this. SAGE will now terminate (sorry). With sage -gdb: sage: time dance(9) h^9 - 27*h^8 + 414*h^7 - 4158*h^6 + 29421*h^5 - 148743*h^4 + 530796*h^3 - 1276992*h^2 + 1866384*h - 1255608 CPU times: user 1786.82 s, sys: 23.05 s, total: 1809.87 s Wall time: 1831.52 sage: time dance(10) Program received signal SIGSEGV, Segmentation fault. [Switching to Thread -1208523072 (LWP 30162)] 0x0064d473 in strlen () from /lib/libc.so.6 (gdb) The program (see below) uses methods from sage.matrix.matrix2.pyx Jaap Hello Jaap, I am looking into this, but I am pressed for time until Thursday, so don't expect any solution before that. It will take forever to valgrind this anyway. If you still have that gdb session it would be great to get a backtrace. I did run the code with smaller parameters, i.e. dance(4) and dance(5), under valgrind and nothing popped up there. So I am suspecting that the code might smash the stack with large parameters, but that ought to be taken with a grain of salt until I get a backtrace and some valgrind output Cheers, Michael ## # Copyright (C) 2006 Jaap Spies, [EMAIL PROTECTED] # # Distributed under the terms of the GNU General Public License (GPL): # # http://www.gnu.org/licenses/ ## Usage from sage sage: attach 'dancing.sage' sage: dance(4) h^4 - 2*h^3 + 9*h^2 - 8*h + 6 # use variable 'h' in the polynomial ring over the rationals h = QQ['h'].gen() def dance(m): Generates the polynomial solutions of the Dancing School Problem Based on a modification of theorem 7.2.1 from Brualdi and Ryser, Combinatorial Matrix Theory. See NAW 5/7 nr. 4 december 2006 p. 285 INPUT: integer m OUTPUT: polynomial in 'h' EXAMPLE: sage: dance(4) h^4 - 2*h^3 + 9*h^2 - 8*h + 6 AUTHOR: Jaap Spies (2006) n = 2*m-2 M = MatrixSpace(ZZ, m, n) A = M([0 for i in range(m*n)]) for i in range(m): for j in range(n): if i j or j i + n - m: A[i,j] = 1 rv = A.rook_vector() # print rv s = sum([(-1)^k*rv[k]*falling_factorial(m+h-k, m-k) for k in range(m+1)]) print s --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: problem with showing plots from command line
Could you give us the output from echo 'LD_LIBRARY_PATH' and 'ldd xdg- open' with and without sourcing sage-env. If you add an 'echo LD_LIBRARY_PATH' right before xdg-open is called in P.show() From the name of the symbol I would guess that it is a libz incompability. There was a patch to the launch code for firefox/ iceweasel that malb made because of a similar issue. Maybe we need to reset LD_LIBRARY_PATH to the old value before we modify it in sage-env in case we launch external helper applications. LD_LIBRARY_PATH (right before xdg-open is called) is /home/bober/sage-2.8.7.2/local/lib/openmpi:/home/bober/sage-2.8.7.2/local/lib/: It isn't actually set to anything normally (outside of sage-env), however. ldd xgd-open won't tell anything (actually, it says that it isn't a dynamic executable) because xdg-open just launched the preferred application. However, when executed from within sage, ldd /usr/bin/eog yields the following possibly offending lines. (The full output is at the end of this email.) libgnutls.so.13 = /home/bober/sage-2.8.7.2/local/lib/libgnutls.so.13 (0xb6f0f000) libfreetype.so.6 = /home/bober/sage-2.8.7.2/local/lib/libfreetype.so.6 (0xb6e36000) libz.so.1 = /home/bober/sage-2.8.7.2/local/lib/libz.so.1 (0xb6e2) libpng12.so.0 = /home/bober/sage-2.8.7.2/local/lib/libpng12.so.0 (0xb6df3000) libgcrypt.so.11 = /home/bober/sage-2.8.7.2/local/lib/libgcrypt.so.11 (0xb6d25000) libgpg-error.so.0 = /home/bober/sage-2.8.7.2/local/lib/libgpg-error.so.0 (0xb6d21000) I realize now that I don't have to go through all of this source editing to find the problem: sage: !eog eog: symbol lookup error: /usr/lib/libxml2.so.2: undefined symbol: gzopen64 sage: !gimp gimp: symbol lookup error: /usr/lib/libcairo.so.2: undefined symbol: FT_Library_SetLcdFilter sage: !gvim gvim: symbol lookup error: /usr/lib/libcairo.so.2: undefined symbol: FT_Library_SetLcdFilter And the problem extends beyond library path errors into python path errors: sage: !glchess Traceback (most recent call last): File /usr/games/glchess, line 18, in module from glchess.glchess import start_game ImportError: No module named glchess.glchess However, calling os.system(LD_LIBRARY_PATH='' eog) or os.system(LD_LIBRARY_PATH='' gimp) works just fine, so a solution might be to just unset LD_LIBRARY_PATH before calling external applications. But there might be a better solution, because I would like for !eog to work, for example. (Well, that's not something that I ever use, but it should work anyway.) output from ldd /usr/bin/eog, just in case there is something I missed: linux-gate.so.1 = (0xe000) /usr/lib/fglrx/libGL.so.1.2.xlibmesa (0xb7ee9000) libpython2.5.so.1.0 = /usr/lib/libpython2.5.so.1.0 (0xb7d9a000) libpthread.so.0 = /lib/tls/i686/cmov/libpthread.so.0 (0xb7d81000) libglade-2.0.so.0 = /usr/lib/libglade-2.0.so.0 (0xb7d69000) liblaunchpad-integration.so.0 = /usr/lib/liblaunchpad-integration.so.0 (0xb7d65000) libgnome-desktop-2.so.2 = /usr/lib/libgnome-desktop-2.so.2 (0xb7d5) libgnomeui-2.so.0 = /usr/lib/libgnomeui-2.so.0 (0xb7cc4000) libgnomevfs-2.so.0 = /usr/lib/libgnomevfs-2.so.0 (0xb7c6a000) libgnome-2.so.0 = /usr/lib/libgnome-2.so.0 (0xb7c55000) libart_lgpl_2.so.2 = /usr/lib/libart_lgpl_2.so.2 (0xb7c3f000) libgconf-2.so.4 = /usr/lib/libgconf-2.so.4 (0xb7c0d000) libgthread-2.0.so.0 = /usr/lib/libgthread-2.0.so.0 (0xb7c08000) libgtk-x11-2.0.so.0 = /usr/lib/libgtk-x11-2.0.so.0 (0xb7883000) libgdk-x11-2.0.so.0 = /usr/lib/libgdk-x11-2.0.so.0 (0xb77fb000) libgdk_pixbuf-2.0.so.0 = /usr/lib/libgdk_pixbuf-2.0.so.0 (0xb77e3000) libcairo.so.2 = /usr/lib/libcairo.so.2 (0xb776c000) libX11.so.6 = /usr/lib/libX11.so.6 (0xb767b000) libgmodule-2.0.so.0 = /usr/lib/libgmodule-2.0.so.0 (0xb7677000) libexif.so.12 = /usr/lib/libexif.so.12 (0xb764d000) liblcms.so.1 = /usr/lib/liblcms.so.1 (0xb761b000) libm.so.6 = /lib/tls/i686/cmov/libm.so.6 (0xb75f6000) libdbus-glib-1.so.2 = /usr/lib/libdbus-glib-1.so.2 (0xb75db000) libgobject-2.0.so.0 = /usr/lib/libgobject-2.0.so.0 (0xb75a) libglib-2.0.so.0 = /usr/lib/libglib-2.0.so.0 (0xb74e3000) libjpeg.so.62 = /usr/lib/libjpeg.so.62 (0xb74c3000) libc.so.6 = /lib/tls/i686/cmov/libc.so.6 (0xb7378000) libxml2.so.2 = /usr/lib/libxml2.so.2 (0xb725a000) libXext.so.6 = /usr/lib/libXext.so.6 (0xb724c000) libXxf86vm.so.1 = /usr/lib/libXxf86vm.so.1 (0xb7247000) libXdamage.so.1 = /usr/lib/libXdamage.so.1 (0xb7244000) libXfixes.so.3 = /usr/lib/libXfixes.so.3 (0xb723f000) libdl.so.2 = /lib/tls/i686/cmov/libdl.so.2 (0xb723a000) libdrm.so.2 = /usr/lib/libdrm.so.2 (0xb723) libutil.so.1 = /lib/tls/i686/cmov/libutil.so.1 (0xb722c000) /lib/ld-linux.so.2
[sage-devel] matrix multiply with huge entries
Hi, I'm interested in multiplying smallish matrices over Z with huge entries. On my machine, sage can multiply 300-bit integers in about 0.14s, and adding integers of that size takes about 1/1000 of the time: sage: x = ZZ.random_element(2^300) sage: y = ZZ.random_element(2^300) sage: timeit z = x * y 10 loops, best of 3: 141 ms per loop sage: timeit z = x + y 1 loops, best of 3: 152 µs per loop So clearly for matrix multiply, we want to Strassen all the way to the bottom. But look at this: sage: M1 = matrix(8, 8, [ZZ.random_element(2^300) for i in range (64)]) sage: M2 = matrix(8, 8, [ZZ.random_element(2^300) for i in range (64)]) sage: time M3 = M1 * M2 CPU times: user 69.43 s, sys: 2.29 s, total: 71.72 s Wall time: 71.76 By my reckoning, it should only have to do 7*7*7 multiplies, which should take 50s. It looks like it's really doing 8*8*8 multiplies. david --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: matrix multiply with huge entries
Is there a way to get the size of an integer (really fast, like a macro getting the number of words)? One could perhaps override _strassen_default_cutoff (though I don't know how much overhead this would be for matrices with smallish entries). One can always enforce it by doing M._multiply_strassen(N) For huge Z, I wonder if it's still trying to do multi-modular? That would probably be bad. I'm also not sure how much of the dispatching is done in Linbox vs. Sage. - Robert On Oct 23, 2007, at 6:17 PM, David Harvey wrote: Hi, I'm interested in multiplying smallish matrices over Z with huge entries. On my machine, sage can multiply 300-bit integers in about 0.14s, and adding integers of that size takes about 1/1000 of the time: sage: x = ZZ.random_element(2^300) sage: y = ZZ.random_element(2^300) sage: timeit z = x * y 10 loops, best of 3: 141 ms per loop sage: timeit z = x + y 1 loops, best of 3: 152 µs per loop So clearly for matrix multiply, we want to Strassen all the way to the bottom. But look at this: sage: M1 = matrix(8, 8, [ZZ.random_element(2^300) for i in range (64)]) sage: M2 = matrix(8, 8, [ZZ.random_element(2^300) for i in range (64)]) sage: time M3 = M1 * M2 CPU times: user 69.43 s, sys: 2.29 s, total: 71.72 s Wall time: 71.76 By my reckoning, it should only have to do 7*7*7 multiplies, which should take 50s. It looks like it's really doing 8*8*8 multiplies. david --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: matrix multiply with huge entries
On Oct 23, 2007, at 9:24 PM, Robert Bradshaw wrote: Is there a way to get the size of an integer (really fast, like a macro getting the number of words)? One could perhaps override _strassen_default_cutoff (though I don't know how much overhead this would be for matrices with smallish entries). I believe mpz_size() is implemented as a macro (at least in the current GMP release), and it returns the number of words. One can always enforce it by doing M._multiply_strassen(N) Ah yes that works nicely: sage: M1 = matrix(4, 4, [ZZ.random_element(2^300) for _ in range (16)]) sage: M2 = matrix(4, 4, [ZZ.random_element(2^300) for _ in range (16)]) sage: time M3 = M1 * M2 CPU times: user 8.68 s, sys: 0.31 s, total: 8.99 s Wall time: 9.00 sage: time M3 = M1._multiply_strassen(M2, 1) CPU times: user 6.84 s, sys: 0.39 s, total: 7.23 s Wall time: 7.32 For huge Z, I wonder if it's still trying to do multi-modular? That would probably be bad. I'm also not sure how much of the dispatching is done in Linbox vs. Sage. Multimodular would be terrible. You don't get any of the benefits of strassen, since the tiny multiplies are way below the strassen cutoff. So basically it would end up looking like doing *integer* multiplication with a multi-modular algorithm, which isn't such a good idea :-) david --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: matrix multiply with huge entries
On 10/23/07, Robert Bradshaw [EMAIL PROTECTED] wrote: Is there a way to get the size of an integer (really fast, like a macro getting the number of words)? One could perhaps override _strassen_default_cutoff (though I don't know how much overhead this would be for matrices with smallish entries). One can always enforce it by doing M._multiply_strassen(N) For huge Z, I wonder if it's still trying to do multi-modular? That would probably be bad. I'm also not sure how much of the dispatching is done in Linbox vs. Sage. Here is the source code for choosing the matrix multiplication algorithm over ZZ, from the matrix_integer_dense.pyx file: cdef sage.structure.element.Matrix _matrix_times_matrix_c_impl(self, sage.structure.element.Matrix right): n = max(self._nrows, self._ncols, right._nrows, right._ncols) if n = 20: return self._multiply_classical(right) a = self.height(); b = right.height() if float(max(a,b)) / float(n) = 0.70: return self._multiply_classical(right) else: return self._multiply_multi_modular(right) - We do have A._multiply_linbox(B), but we never use it by default, since when we first wrapped it sadly turned out to be slower than using our own multi-modular implementation. This is the sort of thing that may change someday, I hope... By my reckoning, it should only have to do 7*7*7 multiplies, which should take 50s. It looks like it's really doing 8*8*8 multiplies. Yep, for your small matrices, Sage is just doing classical matrix multiplication (it's a triply nested for loop later in that file).As Robert points out, just do M1._multiply_strassen(M2, 1) to use our implementation of Strassen with a cutoff of 1. This is indeed faster, as expected: sage: time b = M1 * M2 CPU times: user 33.10 s, sys: 0.05 s, total: 33.15 s Wall time: 33.19 sage: time a = M1._multiply_strassen(M2, 1) CPU times: user 23.86 s, sys: 1.38 s, total: 25.24 s Wall time: 25.66 sage: time c = M1._multiply_linbox(M2) CPU times: user 33.35 s, sys: 0.69 s, total: 34.04 s Wall time: 35.40 --- It could make a lot of sense to make _matrix_times_matrix use strassen when the heights of the input matrices are large, instead of using classical O(n^3) multiplication. Willliam --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: matrix multiply with huge entries
On Oct 23, 6:24 pm, Robert Bradshaw [EMAIL PROTECTED] wrote: Is there a way to get the size of an integer (really fast, like a macro getting the number of words)? One could perhaps override _strassen_default_cutoff (though I don't know how much overhead this would be for matrices with smallish entries). There seem to be two (documented) ways to do this: 1) mpz_sizeinbase(..., 2) gives the number of bits in the number. This will be O(1), but has to count how many bits are used in the highest-order word. mpz_sizeinbase(..., 16) or mpz_sizeinbase(..., 32) may or may not be faster. 2) mpz_size(...) counts the number of words, but then you may have to care about the difference between 32-bit and 64-bit machines. (However, I could imagine that in this case just counting the size in words is the right thing... maybe the cutoff should be twice as many bits on a 64-bit processor.) Carl --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: matrix multiply with huge entries
On Oct 23, 2007, at 6:37 PM, cwitty wrote: On Oct 23, 6:24 pm, Robert Bradshaw [EMAIL PROTECTED] wrote: Is there a way to get the size of an integer (really fast, like a macro getting the number of words)? One could perhaps override _strassen_default_cutoff (though I don't know how much overhead this would be for matrices with smallish entries). There seem to be two (documented) ways to do this: 1) mpz_sizeinbase(..., 2) gives the number of bits in the number. This will be O(1), but has to count how many bits are used in the highest-order word. mpz_sizeinbase(..., 16) or mpz_sizeinbase(..., 32) may or may not be faster. 2) mpz_size(...) counts the number of words, but then you may have to care about the difference between 32-bit and 64-bit machines. (However, I could imagine that in this case just counting the size in words is the right thing... maybe the cutoff should be twice as many bits on a 64-bit processor.) Yes, both of these are functions. It would be nice to at least get the number of limbs via a macro (without using undocumented API or accessing the internals of the mpz_t struct directly (I know how to do that)). - Robert --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: matrix multiply with huge entries
On 10/23/07, David Harvey [EMAIL PROTECTED] wrote: For huge Z, I wonder if it's still trying to do multi-modular? That would probably be bad. I'm also not sure how much of the dispatching is done in Linbox vs. Sage. Multimodular would be terrible. You don't get any of the benefits of strassen, since the tiny multiplies are way below the strassen cutoff. So basically it would end up looking like doing *integer* multiplication with a multi-modular algorithm, which isn't such a good idea :-) It's not doing multi-modular unless that matrix is at least 21 x 21 *and* the coefficients are relatively small compared to the size of the matrix.I at least did some tiny amount of tuning for this function (at the airport in Calgary, now that I think about it). Vastly more could be done. I just looked at the code in matrix_modn_dense.pyx for matrix multiply, and we don't use linbox there either yet. We just use strassen for big matrices and classical multiplication for small matrices. We did wrap linbox, but your/my/Robert's implementation of strassen in Sage (which is what we use), seems to be a bit better whenever I do timings: sage: m1 = random_matrix(GF(10007), 800) sage: m2 = random_matrix(GF(10007), 800) sage: time c = m1*m2 CPU times: user 0.82 s, sys: 0.03 s, total: 0.85 s Wall time: 0.85 sage: time d = m1._multiply_linbox(m2) CPU times: user 1.14 s, sys: 0.02 s, total: 1.16 s Wall time: 1.17 sage: c == d True sage: time e = m1._multiply_classical(m2) CPU times: user 3.44 s, sys: 0.00 s, total: 3.44 s Wall time: 3.44 Hopefully when Clement gets here in January, I can show him this and he'll get so annoyed he'll show us how to use linbox correctly, and we'll switch to using linbox for multiplication. It's very important to keep in mind that the above timing is really Sage using Linbox which means there is data conversion going on, along with issues involving us possibly not optimally building Linbox yet. Also, very often we have chosen using only functions from Linbox that demonstrably work very reliably on all Sage supported platforms. I think the main use of linbox from Sage now is for charpoly and det computation. Though both are unfortunately nonoptimal right now because of regressions in Linbox (we found bugs, they temporarily fixed them by making some things slower...), which I think might have been resolved very recently. 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: matrix multiply with huge entries
On Oct 23, 2007, at 9:47 PM, William Stein wrote: On 10/23/07, David Harvey [EMAIL PROTECTED] wrote: For huge Z, I wonder if it's still trying to do multi-modular? That would probably be bad. I'm also not sure how much of the dispatching is done in Linbox vs. Sage. Multimodular would be terrible. You don't get any of the benefits of strassen, since the tiny multiplies are way below the strassen cutoff. So basically it would end up looking like doing *integer* multiplication with a multi-modular algorithm, which isn't such a good idea :-) It's not doing multi-modular unless that matrix is at least 21 x 21 *and* the coefficients are relatively small compared to the size of the matrix.I at least did some tiny amount of tuning for this function (at the airport in Calgary, now that I think about it). Vastly more could be done. I just looked at the code in matrix_modn_dense.pyx for matrix multiply, and we don't use linbox there either yet. We just use strassen for big matrices and classical multiplication for small matrices. Actually, soon I will be doing matrix multiply over Z/p^N for some large N, so the matrix_modn_dense thing is relevant. Another question: for large moduli like this, does it delay the reduction until after the adds/subs, either in classical or strassen? This would mean only O(n^2) reductions instead of O(n^3). david --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: matrix multiply with huge entries
On Oct 23, 2007, at 6:51 PM, David Harvey wrote: On Oct 23, 2007, at 9:47 PM, William Stein wrote: On 10/23/07, David Harvey [EMAIL PROTECTED] wrote: For huge Z, I wonder if it's still trying to do multi-modular? That would probably be bad. I'm also not sure how much of the dispatching is done in Linbox vs. Sage. Multimodular would be terrible. You don't get any of the benefits of strassen, since the tiny multiplies are way below the strassen cutoff. So basically it would end up looking like doing *integer* multiplication with a multi-modular algorithm, which isn't such a good idea :-) It's not doing multi-modular unless that matrix is at least 21 x 21 *and* the coefficients are relatively small compared to the size of the matrix.I at least did some tiny amount of tuning for this function (at the airport in Calgary, now that I think about it). Vastly more could be done. I just looked at the code in matrix_modn_dense.pyx for matrix multiply, and we don't use linbox there either yet. We just use strassen for big matrices and classical multiplication for small matrices. Actually, soon I will be doing matrix multiply over Z/p^N for some large N, so the matrix_modn_dense thing is relevant. Another question: for large moduli like this, does it delay the reduction until after the adds/subs, either in classical or strassen? This would mean only O(n^2) reductions instead of O(n^3). I don't think there is any special code for matrix_mod_n for n larger than a word (or perhaps even half a word). For the classical, it delays doing reductions when computing the dot product until the last moment. - Robert --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: matrix multiply with huge entries
Hi everyone, We do have A._multiply_linbox(B), but we never use it by default, since when we first wrapped it sadly turned out to be slower than using our own multi-modular implementation. This is the sort of thing that may change someday, I hope... Yep, that should change pretty soon! I was actually planning to spend some time looking at this pb of small matrices with huge ints. Strassen-Winograd is fine for dimensions 2^k but if with odd dimension, it can be better to use other algorithms (3x3 splitting for example, Pan algorithms, Winograd PreStrassen algorithm, and some personnal ideas too). Therefore it would be nice to have a kind of database of the best algorithm (in term of # of mul) for each small dimension (2,3,4,5,6,7...) and have a preprocessing phase that would choose the good combination of these algorithms, for any given n. Clement --- It could make a lot of sense to make _matrix_times_matrix use strassen when the heights of the input matrices are large, instead of using classical O(n^3) multiplication. Willliam --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: matrix multiply with huge entries
Actually, soon I will be doing matrix multiply over Z/p^N for some large N, so the matrix_modn_dense thing is relevant. Maybe, but unfortunately matrix_modn_dense is only for small p. Another question: for large moduli like this, does it delay the reduction until after the adds/subs, either in classical or strassen? This would mean only O(n^2) reductions instead of O(n^3). matrix_modn_dense does do delayed mod. But it's only mod p for smallish p. You'll likely have to create a new class such as matrix_modbign_dense or something. Don't call it matrix_modN_dense :-). -- 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] DSage server: start clean?
I start a DSage server, then add several jobs to it, then kill SAGE. Then I start DSage up again, and start workers. These workers go after the dead jobs! Maybe this is a feature? How do I get a clean DSage server? Thanks, JV --~--~-~--~~~---~--~~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Re: DSage server: start clean?
On 10/23/07, John Voight [EMAIL PROTECTED] wrote: I think I figured out a brutal way: Just delete the $HOME/.dsage/dsage directory! There must be a better way... I had precisely the same complaint very recently, and Yi added a new command to deal with exactly this problem: sage: d = DSage()# connect to the server you want to clear sage: d.kill_all() # remove all jobs from the job queue -- 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
[sage-devel] Notices this month
Hi, Our opinion piece Open Source Mathematical Software appeared in the Notices of the AMS this month: http://www.ams.org/notices/200710/ The link to the article is on the upper-right corner of the page. Thanks to everybody who helped with the article! -- 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~--~~~~--~~--~--~---
