Menu
▾
▴
flint-devel
|
From: Bill H. <goo...@go...> - 2009-07-06 02:22:32
|
I've just released FLINT 1.4. Get it at http://www.flintlib.org/ This release contains a large number of *****speedups*****. Note that the zmod_poly_gcd, xgcd, gcd_invert and resultant speedups also speed up the associated fmpz_poly functions. The gcd_invert, resultant and xgcd speedups are asymptotically fast and practically much faster. The gcd functions are much faster than they were. Here is a graph comparing zmod_poly_gcd with Magma: http://sage.math.washington.edu/home/wbhart/zpgcd8.png And here is one comparing fmpz_poly_gcd with Magma (note the scale is a factor of 20 for the brightest points!!): http://sage.math.washington.edu/home/wbhart/gcd.png There are also some *****critical bug fixes****** in this release. Users are advised to update to the latest version. Here is a summary of the changes and additions in this release: * Sped up zmod_poly division in case where operands are the same length * Sped up zmod_poly division in case where operands have lengths differing by 1 * Fixed a bug in zmod_poly_gcd for polynomials of zero length * Sped up zmod_poly_gcd considerably (both euclidean and half gcd) * Sped up zmod_poly_gcd_invert and zmod_poly_xgcd considerably * Made zmod_poly_gcd_invert and zmod_poly_xgcd asymptotically fast * Made zmod_poly_resultant asymptotically fast * Added optimised zmod_poly_rem function * Fixed a divide by zero bug in zmod_poly_factor_berlekamp * Added test code for z_factor_tinyQS and z_factor_HOLF * Fixed many bugs in the z_factor code, tinyQS and mpQS * Corrected numerous typos in the documentation and added missing descriptions * Added F_mpz_cmp function * Added documentation to the manual for the new F_mpz module As usual I have tested on 64 and 32 bit machines, including Cygwin and valgrinded the new code. There should be a FLINT 1.5 before FLINT 2.0 comes out towards the end of this year. In particular I need to address: * The zmod_poly_factor function is still waaaay slower than Magma - probably due to Magma having fast linear algebra over Z/pZ, including strassen multiplication * The fmpz_poly_divrem function is not asymptotically fast (there is still a log factor which can be removed by using newton iteration) - though we still beat Magma everywhere * The fmpz_poly_pseudo_rem function is not asymptotically fast at all, it is quadratic time * There is no fmpz_poly_rem function * We don't have zmod_poly_compose or zmod_poly_evaluate yet * The heuristic fmpz_poly_gcd tricks need to be propagated to xgcd, resultant and invmod functions and even the division functions * We don't have a modular division algorithm yet Enjoy!! Bill. |
|
From: Burcin E. <bu...@er...> - 2009-07-06 12:11:10
|
Hi Bill, On Mon, 6 Jul 2009 03:16:52 +0100 Bill Hart <goo...@go...> wrote: > I've just released FLINT 1.4. Get it at http://www.flintlib.org/ <snip release info> > There should be a FLINT 1.5 before FLINT 2.0 comes out towards the end > of this year. In particular I need to address: > <snip> > * We don't have zmod_poly_compose or zmod_poly_evaluate yet Can I also request fmpz_poly_evaluate_mod? I posted a patch implementing this here, but I guess it got lost in the bug discussion: http://sourceforge.net/mailarchive/forum.php?thread_name=20090331192030.7634e082%40karr&forum_name=flint-devel As I wrote in that message, I also need to "translate" polynomials (i.e., compose with x+k for some constant k) very often. I am not sure if it's worth introducing new functions for this purpose, since they can be handled as a special case of composition. Though I still need fmpz_poly_compose_mod in that case. Here is a cython file with some of these functions: http://sage.math.washington.edu/home/burcin/sage_extras.pyx This is a part of a patch to Sage to add fast nullspace computation over QQ(x). It would be great if this functionality was added to FLINT before I submit the patch to Sage. :) Thanks. Burcin |
|
From: Bill H. <goo...@go...> - 2009-07-06 13:18:25
|
Hi Burcin, indeed I missed the patch attached to that flint-devel post. I think I can fairly easily add the stuff you implemented in cython, directly to FLINT. I'll do hat in the next few days and issue FLINT 1.4.1 when I have done it. Bill. 2009/7/6 Burcin Erocal <bu...@er...>: > Hi Bill, > > On Mon, 6 Jul 2009 03:16:52 +0100 > Bill Hart <goo...@go...> wrote: > >> I've just released FLINT 1.4. Get it at http://www.flintlib.org/ > <snip release info> >> There should be a FLINT 1.5 before FLINT 2.0 comes out towards the end >> of this year. In particular I need to address: >> > <snip> >> * We don't have zmod_poly_compose or zmod_poly_evaluate yet > > Can I also request fmpz_poly_evaluate_mod? > > I posted a patch implementing this here, but I guess it got lost in > the bug discussion: > > http://sourceforge.net/mailarchive/forum.php?thread_name=20090331192030.7634e082%40karr&forum_name=flint-devel > > As I wrote in that message, I also need to "translate" polynomials > (i.e., compose with x+k for some constant k) very often. I am not sure > if it's worth introducing new functions for this purpose, since they > can be handled as a special case of composition. Though I still need > fmpz_poly_compose_mod in that case. > > Here is a cython file with some of these functions: > > http://sage.math.washington.edu/home/burcin/sage_extras.pyx > > > This is a part of a patch to Sage to add fast nullspace computation > over QQ(x). It would be great if this functionality was added to FLINT > before I submit the patch to Sage. :) > > > Thanks. > > Burcin > > ------------------------------------------------------------------------------ > _______________________________________________ > flint-devel mailing list > fli...@li... > https://lists.sourceforge.net/lists/listinfo/flint-devel > |
|
From: Bill H. <goo...@go...> - 2009-07-16 02:52:29
|
Hi Burcin, I've added the functions you supplied, to fmpz_poly.c/h in trunk. At your leisure, could you verify they actually work with your code. I've made some minor changes to them, but I haven't added test code or documentation (feel free to supply it if you feel that the functions could be of more general use). Once you are happy with them, I'll make the release tarball. I'm sure you have your git repo hooked up to the FLINT svn, but if not, here is the FLINT trunk: http://flint.svn.sourceforge.net/svnroot/flint/trunk Bill. 2009/7/6 Bill Hart <goo...@go...>: > Hi Burcin, indeed I missed the patch attached to that flint-devel post. > > I think I can fairly easily add the stuff you implemented in cython, > directly to FLINT. > > I'll do hat in the next few days and issue FLINT 1.4.1 when I have done it. > > Bill. > > 2009/7/6 Burcin Erocal <bu...@er...>: >> Hi Bill, >> >> On Mon, 6 Jul 2009 03:16:52 +0100 >> Bill Hart <goo...@go...> wrote: >> >>> I've just released FLINT 1.4. Get it at http://www.flintlib.org/ >> <snip release info> >>> There should be a FLINT 1.5 before FLINT 2.0 comes out towards the end >>> of this year. In particular I need to address: >>> >> <snip> >>> * We don't have zmod_poly_compose or zmod_poly_evaluate yet >> >> Can I also request fmpz_poly_evaluate_mod? >> >> I posted a patch implementing this here, but I guess it got lost in >> the bug discussion: >> >> http://sourceforge.net/mailarchive/forum.php?thread_name=20090331192030.7634e082%40karr&forum_name=flint-devel >> >> As I wrote in that message, I also need to "translate" polynomials >> (i.e., compose with x+k for some constant k) very often. I am not sure >> if it's worth introducing new functions for this purpose, since they >> can be handled as a special case of composition. Though I still need >> fmpz_poly_compose_mod in that case. >> >> Here is a cython file with some of these functions: >> >> http://sage.math.washington.edu/home/burcin/sage_extras.pyx >> >> >> This is a part of a patch to Sage to add fast nullspace computation >> over QQ(x). It would be great if this functionality was added to FLINT >> before I submit the patch to Sage. :) >> >> >> Thanks. >> >> Burcin >> >> ------------------------------------------------------------------------------ >> _______________________________________________ >> flint-devel mailing list >> fli...@li... >> https://lists.sourceforge.net/lists/listinfo/flint-devel >> > |
|
From: Bill H. <goo...@go...> - 2009-07-16 02:57:05
|
I forgot to mention, I implemented zmod_poly_compose and zmod_poly_evaluate (supplied with test code and docs). One small inefficiency in the evaluate_mod code is that we reduce multiple coefficients mod p, but don't use the same precomputed inverse in each case. We really need an fmpz_mod_ui_precomp or something like that. Otherwise I think what you have is fairly efficient. One other major improvement would be divide and conquer for zmod_poly_compose. This would actually be asymptotically faster I believe. In the case of zmod_poly_evaluate, I believe Horner's method is asymptotically fast. I don't know if translate would be faster with a divide and conquer strategy. Bill. 2009/7/16 Bill Hart <goo...@go...>: > Hi Burcin, > > I've added the functions you supplied, to fmpz_poly.c/h in trunk. At > your leisure, could you verify they actually work with your code. I've > made some minor changes to them, but I haven't added test code or > documentation (feel free to supply it if you feel that the functions > could be of more general use). > > Once you are happy with them, I'll make the release tarball. > > I'm sure you have your git repo hooked up to the FLINT svn, but if > not, here is the FLINT trunk: > > http://flint.svn.sourceforge.net/svnroot/flint/trunk > > Bill. > > 2009/7/6 Bill Hart <goo...@go...>: >> Hi Burcin, indeed I missed the patch attached to that flint-devel post. >> >> I think I can fairly easily add the stuff you implemented in cython, >> directly to FLINT. >> >> I'll do hat in the next few days and issue FLINT 1.4.1 when I have done it. >> >> Bill. >> >> 2009/7/6 Burcin Erocal <bu...@er...>: >>> Hi Bill, >>> >>> On Mon, 6 Jul 2009 03:16:52 +0100 >>> Bill Hart <goo...@go...> wrote: >>> >>>> I've just released FLINT 1.4. Get it at http://www.flintlib.org/ >>> <snip release info> >>>> There should be a FLINT 1.5 before FLINT 2.0 comes out towards the end >>>> of this year. In particular I need to address: >>>> >>> <snip> >>>> * We don't have zmod_poly_compose or zmod_poly_evaluate yet >>> >>> Can I also request fmpz_poly_evaluate_mod? >>> >>> I posted a patch implementing this here, but I guess it got lost in >>> the bug discussion: >>> >>> http://sourceforge.net/mailarchive/forum.php?thread_name=20090331192030.7634e082%40karr&forum_name=flint-devel >>> >>> As I wrote in that message, I also need to "translate" polynomials >>> (i.e., compose with x+k for some constant k) very often. I am not sure >>> if it's worth introducing new functions for this purpose, since they >>> can be handled as a special case of composition. Though I still need >>> fmpz_poly_compose_mod in that case. >>> >>> Here is a cython file with some of these functions: >>> >>> http://sage.math.washington.edu/home/burcin/sage_extras.pyx >>> >>> >>> This is a part of a patch to Sage to add fast nullspace computation >>> over QQ(x). It would be great if this functionality was added to FLINT >>> before I submit the patch to Sage. :) >>> >>> >>> Thanks. >>> >>> Burcin >>> >>> ------------------------------------------------------------------------------ >>> _______________________________________________ >>> flint-devel mailing list >>> fli...@li... >>> https://lists.sourceforge.net/lists/listinfo/flint-devel >>> >> > |
|
From: Burcin E. <bu...@er...> - 2009-07-27 20:00:39
|
Hi Bill, On Thu, 16 Jul 2009 03:52:21 +0100 Bill Hart <goo...@go...> wrote: > I've added the functions you supplied, to fmpz_poly.c/h in trunk. At > your leisure, could you verify they actually work with your code. I've > made some minor changes to them, but I haven't added test code or > documentation (feel free to supply it if you feel that the functions > could be of more general use). > > Once you are happy with them, I'll make the release tarball. I finally found the time to test the new functions. Everything seems to work fine, so I'm happy. :) I can try to write test code, and/or documentation tomorrow. Is there any convention or instructions on writing tests in FLINT? Should I just pick random polynomials and values, evaluate things using the functions and "by hand", then check the results? > I'm sure you have your git repo hooked up to the FLINT svn, but if > not, here is the FLINT trunk: > > http://flint.svn.sourceforge.net/svnroot/flint/trunk I am not really an advanced git/hg/svn guy. I might try doing this with hg tomorrow, or just generate patches the old fashioned way. > One other major improvement would be divide and conquer for > zmod_poly_compose. This would actually be asymptotically faster I > believe. In the case of zmod_poly_evaluate, I believe Horner's method > is asymptotically fast. I don't know if translate would be faster with > a divide and conquer strategy. The paper I referred to earlier, http://doi.acm.org/10.1145/258726.258745 suggests that method D "Paterson & Stockmeyer's (1973) method" is asymptotically faster than divide & conquer or Horner's. I am sure I'll have bigger problems elsewhere if I have to translate polynomials of degree ~512 though. Many thanks. Burcin |
|
From: Bill H. <goo...@go...> - 2009-07-27 20:32:16
|
Hi Burcin, Great that everything works. The easiest way to write a test function is to cut and paste an existing one. It shouldn't be too hard to convert random poly to zmod_polys then use the evaluate or composition functions there, then compare the results. In some cases it is hard to do randomised testing because it is difficult to find a simpler way of writing the function so that you have a trusted implementation to compare against. In such cases I tend to look for some algebraic way of testing the result, e.g. Test addition by subtracting the addend back off and see if you get the same thing back. I rarely check individual cases but try to implement the randomised testing in such a way as to pick up corner cases. I don't actually have HG, but I can accept patches in git, svn or standard patch format. If it would help, I can easily give you svn access, if you have a sourceforge account. Bill. On 27/07/2009, Burcin Erocal <bu...@er...> wrote: > Hi Bill, > > On Thu, 16 Jul 2009 03:52:21 +0100 > Bill Hart <goo...@go...> wrote: > >> I've added the functions you supplied, to fmpz_poly.c/h in trunk. At >> your leisure, could you verify they actually work with your code. I've >> made some minor changes to them, but I haven't added test code or >> documentation (feel free to supply it if you feel that the functions >> could be of more general use). >> >> Once you are happy with them, I'll make the release tarball. > > I finally found the time to test the new functions. Everything seems to > work fine, so I'm happy. :) > > I can try to write test code, and/or documentation tomorrow. Is there > any convention or instructions on writing tests in FLINT? Should I just > pick random polynomials and values, evaluate things using the functions > and "by hand", then check the results? > > >> I'm sure you have your git repo hooked up to the FLINT svn, but if >> not, here is the FLINT trunk: >> >> http://flint.svn.sourceforge.net/svnroot/flint/trunk > > I am not really an advanced git/hg/svn guy. I might try doing this with > hg tomorrow, or just generate patches the old fashioned way. > > >> One other major improvement would be divide and conquer for >> zmod_poly_compose. This would actually be asymptotically faster I >> believe. In the case of zmod_poly_evaluate, I believe Horner's method >> is asymptotically fast. I don't know if translate would be faster with >> a divide and conquer strategy. > > The paper I referred to earlier, > > http://doi.acm.org/10.1145/258726.258745 > > suggests that method D "Paterson & Stockmeyer's (1973) method" is > asymptotically faster than divide & conquer or Horner's. I am sure I'll > have bigger problems elsewhere if I have to translate polynomials of > degree ~512 though. > > > Many thanks. > > Burcin > > ------------------------------------------------------------------------------ > _______________________________________________ > flint-devel mailing list > fli...@li... > https://lists.sourceforge.net/lists/listinfo/flint-devel > |
|
From: Burcin E. <bu...@er...> - 2009-08-08 10:13:26
Attachments:
test_translate_functions.patch
|
Hi Bill, On Mon, 27 Jul 2009 21:32:05 +0100 Bill Hart <goo...@go...> wrote: > Great that everything works. The easiest way to write a test function > is to cut and paste an existing one. It shouldn't be too hard to > convert random poly to zmod_polys then use the evaluate or composition > functions there, then compare the results. In some cases it is hard to > do randomised testing because it is difficult to find a simpler way of > writing the function so that you have a trusted implementation to > compare against. In such cases I tend to look for some algebraic way > of testing the result, e.g. Test addition by subtracting the addend > back off and see if you get the same thing back. I rarely check > individual cases but try to implement the randomised testing in such a > way as to pick up corner cases. After another long delay, I managed to write the test functions and the documentation. See the attached patch. For testing, I just used the already existing functions in the library. For example, in order to test fmpz_poly_evaluate_mod I call fmpz_poly_evaluate then reduce the result. I would be happy to revise the patch if you have any suggestions. > I don't actually have HG, but I can accept patches in git, svn or > standard patch format. > > If it would help, I can easily give you svn access, if you have a > sourceforge account. I like to know that my patches are being reviewed. Committing directly to SVN would eliminate that step. Though if you think this process is taking up too much time, and the possibility that I mess up the repository is low enough, my sf user name is burcin. Thanks. Burcin |
|
From: Bill H. <goo...@go...> - 2009-08-08 15:52:47
|
Hi Burcin, Thanks for the patch. I'll still review all the code going into FLINT. But it is then easier for you to commit directly. FLINT is currently like a heart patient, laid out on the table in pieces in the middle of surgery. But in a week or so I hope to have it back together and sewn up for the release. Most of the changes only affect FLINT 2.0 code, which is not being released yet. But it affects the F_mpz layer, which I have released. The way you've done the test function is fine by the way. It is what I would do. I guess your patch is against FLINT 1.4 rather than trunk, is that correct? Bill. 2009/8/8 Burcin Erocal <bu...@er...>: > Hi Bill, > > On Mon, 27 Jul 2009 21:32:05 +0100 > Bill Hart <goo...@go...> wrote: > >> Great that everything works. The easiest way to write a test function >> is to cut and paste an existing one. It shouldn't be too hard to >> convert random poly to zmod_polys then use the evaluate or composition >> functions there, then compare the results. In some cases it is hard to >> do randomised testing because it is difficult to find a simpler way of >> writing the function so that you have a trusted implementation to >> compare against. In such cases I tend to look for some algebraic way >> of testing the result, e.g. Test addition by subtracting the addend >> back off and see if you get the same thing back. I rarely check >> individual cases but try to implement the randomised testing in such a >> way as to pick up corner cases. > > After another long delay, I managed to write the test functions and the > documentation. See the attached patch. > > For testing, I just used the already existing functions in the library. > For example, in order to test fmpz_poly_evaluate_mod I call > fmpz_poly_evaluate then reduce the result. > > I would be happy to revise the patch if you have any suggestions. > >> I don't actually have HG, but I can accept patches in git, svn or >> standard patch format. >> >> If it would help, I can easily give you svn access, if you have a >> sourceforge account. > > I like to know that my patches are being reviewed. Committing directly > to SVN would eliminate that step. Though if you think this process is > taking up too much time, and the possibility that I mess up the > repository is low enough, my sf user name is burcin. > > Thanks. > > Burcin > ------------------------------------------------------------------------------ > Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day > trial. Simplify your report design, integration and deployment - and focus on > what you do best, core application coding. Discover what's new with > Crystal Reports now. http://p.sf.net/sfu/bobj-july > _______________________________________________ > flint-devel mailing list > fli...@li... > https://lists.sourceforge.net/lists/listinfo/flint-devel > > |
|
From: Burcin E. <bu...@er...> - 2009-08-08 16:24:12
|
On Sat, 8 Aug 2009 16:52:36 +0100 Bill Hart <goo...@go...> wrote: > Hi Burcin, > > Thanks for the patch. I'll still review all the code going into FLINT. > But it is then easier for you to commit directly. > > FLINT is currently like a heart patient, laid out on the table in > pieces in the middle of surgery. But in a week or so I hope to have it > back together and sewn up for the release. Most of the changes only > affect FLINT 2.0 code, which is not being released yet. But it affects > the F_mpz layer, which I have released. > > The way you've done the test function is fine by the way. It is what I > would do. > > I guess your patch is against FLINT 1.4 rather than trunk, is that > correct? It's against trunk. I don't think the new functions are available in the 1.4 branch. Will the new release be from trunk? or in other words, will it have these functions? Thank you. Burcin |
|
From: Bill H. <goo...@go...> - 2009-08-08 19:57:28
|
2009/8/8 Burcin Erocal <bu...@er...>: > On Sat, 8 Aug 2009 16:52:36 +0100 > Bill Hart <goo...@go...> wrote: > >> Hi Burcin, >> >> Thanks for the patch. I'll still review all the code going into FLINT. >> But it is then easier for you to commit directly. >> >> FLINT is currently like a heart patient, laid out on the table in >> pieces in the middle of surgery. But in a week or so I hope to have it >> back together and sewn up for the release. Most of the changes only >> affect FLINT 2.0 code, which is not being released yet. But it affects >> the F_mpz layer, which I have released. >> >> The way you've done the test function is fine by the way. It is what I >> would do. >> >> I guess your patch is against FLINT 1.4 rather than trunk, is that >> correct? > > It's against trunk. I don't think the new functions are available in > the 1.4 branch. Great. > > Will the new release be from trunk? or in other words, will it have > these functions? Yes, it will. > > Thank you. > > Burcin > Bill. |
Thanks for helping keep SourceForge clean.
X