[sage-devel] Support Vector Machine
130 views
Skip to first unread message
William Cauchois
May 4, 2010, 2:11:05 PM5/4/10
to sage-devel
Hi everyone,
As part of another project, I completed a rudimentary Python binding
to Thorsten Joachims' SVM-Light library (http://
svmlight.joachims.org/) implementing a Support Vector Machine. My
source code is available at
http://bitbucket.org/wcauchois/pysvmlight
Are there people doing ML research who would be interested in having
access to SVM-Light from inside Sage? Is there anyone who would like
to help me get PySVMLight into a more feature-complete state and then
integrate it with Sage?
-- Bill
--
To post to this group, send an email to sage-...@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
As part of another project, I completed a rudimentary Python binding
to Thorsten Joachims' SVM-Light library (http://
svmlight.joachims.org/) implementing a Support Vector Machine. My
source code is available at
http://bitbucket.org/wcauchois/pysvmlight
Are there people doing ML research who would be interested in having
access to SVM-Light from inside Sage? Is there anyone who would like
to help me get PySVMLight into a more feature-complete state and then
integrate it with Sage?
-- Bill
--
To post to this group, send an email to sage-...@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
William Stein
May 4, 2010, 2:34:58 PM5/4/10
to sage-...@googlegroups.com
On Tue, May 4, 2010 at 11:11 AM, William Cauchois <wcau...@gmail.com> wrote:
> Hi everyone,
>
> As part of another project, I completed a rudimentary Python binding
> to Thorsten Joachims' SVM-Light library (http://
> svmlight.joachims.org/) implementing a Support Vector Machine. My
> source code is available at
>
> http://bitbucket.org/wcauchois/pysvmlight
>
> Are there people doing ML research who would be interested in having
> access to SVM-Light from inside Sage? Is there anyone who would like
> to help me get PySVMLight into a more feature-complete state and then
> integrate it with Sage?
>
Could you write a little more to sage-devel about why mathematicians
> Hi everyone,
>
> As part of another project, I completed a rudimentary Python binding
> to Thorsten Joachims' SVM-Light library (http://
> svmlight.joachims.org/) implementing a Support Vector Machine. My
> source code is available at
>
> http://bitbucket.org/wcauchois/pysvmlight
>
> Are there people doing ML research who would be interested in having
> access to SVM-Light from inside Sage? Is there anyone who would like
> to help me get PySVMLight into a more feature-complete state and then
> integrate it with Sage?
>
might care about "support vector machines" -- it's possible that most
people reading this have never heard of them.
William
Martin Albrecht
May 4, 2010, 3:10:16 PM5/4/10
to sage-...@googlegroups.com
On Tuesday 04 May 2010, William Stein wrote:
> On Tue, May 4, 2010 at 11:11 AM, William Cauchois <wcau...@gmail.com>
wrote:
> > Hi everyone,
> >
> > As part of another project, I completed a rudimentary Python binding
> > to Thorsten Joachims' SVM-Light library (http://
> > svmlight.joachims.org/) implementing a Support Vector Machine. My
> > source code is available at
> >
> > http://bitbucket.org/wcauchois/pysvmlight
> >
> > Are there people doing ML research who would be interested in having
> > access to SVM-Light from inside Sage? Is there anyone who would like
> > to help me get PySVMLight into a more feature-complete state and then
> > integrate it with Sage?
>
> Could you write a little more to sage-devel about why mathematicians
> might care about "support vector machines" -- it's possible that most
> people reading this have never heard of them.
Since I'm nowhere near an expert, here's the first paragraph from Wikipedia:
> On Tue, May 4, 2010 at 11:11 AM, William Cauchois <wcau...@gmail.com>
wrote:
> > Hi everyone,
> >
> > As part of another project, I completed a rudimentary Python binding
> > to Thorsten Joachims' SVM-Light library (http://
> > svmlight.joachims.org/) implementing a Support Vector Machine. My
> > source code is available at
> >
> > http://bitbucket.org/wcauchois/pysvmlight
> >
> > Are there people doing ML research who would be interested in having
> > access to SVM-Light from inside Sage? Is there anyone who would like
> > to help me get PySVMLight into a more feature-complete state and then
> > integrate it with Sage?
>
> Could you write a little more to sage-devel about why mathematicians
> might care about "support vector machines" -- it's possible that most
> people reading this have never heard of them.
"""
Support vector machines (SVMs) are a set of related supervised learning
methods used for classification and regression. In simple words, given a set
of training examples, each marked as belonging to one of two categories, an
SVM training algorithm builds a model that predicts whether a new example
falls into one category or the other. Intuitively, an SVM model is a
representation of the examples as points in space, mapped so that the examples
of the separate categories are divided by a clear gap that is as wide as
possible. New examples are then mapped into that same space and predicted to
belong to a category based on which side of the gap they fall on.
"""
http://en.wikipedia.org/wiki/Support_vector_machine
I recently played around with SVM in the context of cryptanalysis to
distinguish plaintext-ciphertext pairs with certain "good" properties from
others as part of an attack. For that I actually wrote a little Sage script :)
I assume SVMs could be useful to classify experimental data etc. in other
contexts too.
Btw. I came across SVMs in the context of author identification: you extract
features such as sentence length and then use those feature vectors to decide
whether an anonymous text was written by A or B. The idea is that you do not
need to build a model yourself, the algorithm will attempt to separate your
training sets as much as possible.
I'd like to see some optional SPKG which provides SVM support. However, in the
foreseeable future I won't be able to help much since I'm supposed to work on
my thesis.
Cheers,
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://www.informatik.uni-bremen.de/~malb
_jab: martinr...@jabber.ccc.de
William Cauchois
May 4, 2010, 10:38:35 PM5/4/10
to sage-devel
Sure. Let me elaborate.
A support vector machine is a type of machine learning algorithm. ML
algorithms are usually used for classification -- train some sort of
model and then use it to classify unknown instances. For my research
project (for example), we used an SVM to categorize DOM elements --
say you want to get a list of all of the phone numbers on a page; our
program can (given a few training examples) do just that using SVM-
Light (through my Python binding).
ML algorithms have tons of applications, but I'm not really an expert
here. Maybe someone else can contribute their experiences with ML in
general or SVMs in particular. Support vector machines are a very
versatile and generic type of ML algo.
On May 4, 11:34 am, William Stein <wst...@gmail.com> wrote:
A support vector machine is a type of machine learning algorithm. ML
algorithms are usually used for classification -- train some sort of
model and then use it to classify unknown instances. For my research
project (for example), we used an SVM to categorize DOM elements --
say you want to get a list of all of the phone numbers on a page; our
program can (given a few training examples) do just that using SVM-
Light (through my Python binding).
ML algorithms have tons of applications, but I'm not really an expert
here. Maybe someone else can contribute their experiences with ML in
general or SVMs in particular. Support vector machines are a very
versatile and generic type of ML algo.
On May 4, 11:34 am, William Stein <wst...@gmail.com> wrote:
William Cauchois
May 4, 2010, 10:41:54 PM5/4/10
to sage-devel
On May 4, 12:10 pm, Martin Albrecht <m...@informatik.uni-bremen.de>
wrote:
Thanks for sharing your experiences. An optional SPKG sounds like the
way to go. Could you point me to any resources describing how to go
about creating an SPKG? Another thing I'm not clear on is how to
integrate a Python C extension with Sage. There must be some SPKGs
that do this, so maybe I could look at that source code.
wrote:
> On Tuesday 04 May 2010, William Stein wrote:
>
>
>
>
>
> > On Tue, May 4, 2010 at 11:11 AM, William Cauchois <wcauch...@gmail.com>
>
>
>
>
>
way to go. Could you point me to any resources describing how to go
about creating an SPKG? Another thing I'm not clear on is how to
integrate a Python C extension with Sage. There must be some SPKGs
that do this, so maybe I could look at that source code.
Sergey Bochkanov
May 5, 2010, 3:42:49 AM5/5/10
to William Stein
Hello, William.
You wrote 4 мая 2010 г., 22:34:58:
> Could you write a little more to sage-devel about why mathematicians
> might care about "support vector machines" -- it's possible that most
> people reading this have never heard of them.
Being sage-devel reader for a while I may say that SAGE users are
mostly interested in symbolic algebra, graph theory, other kinds of
"exact algebra" (finite rings, etc.). Interest in numerical processing
is much more lower.
Looks like we (Open Source Community) have:
* R - for statistical processing
* Octave - for numerical processing
* SAGE - for symbolic/"exact" problems
What do you think about such specialization? Is it intentional?
P.S. I've thought on writing SAGEable Python wrapper for ALGLIB. This
idea came to me when I worked with automatically generated C# wrapper
for MPIR. It started as MPIR-related project, but now I see that the
same technology can be applied to other software projects.
I know that SAGE already has GSL wrapper, but two projects don't
overlap each other. Some functionality is present only in GSL, some -
only in ALGLIB. But is numerical analysis really needed in the SAGE?
--
With best regards,
Sergey mailto:sergey.b...@alglib.net
You wrote 4 мая 2010 г., 22:34:58:
> Could you write a little more to sage-devel about why mathematicians
> might care about "support vector machines" -- it's possible that most
> people reading this have never heard of them.
mostly interested in symbolic algebra, graph theory, other kinds of
"exact algebra" (finite rings, etc.). Interest in numerical processing
is much more lower.
Looks like we (Open Source Community) have:
* R - for statistical processing
* Octave - for numerical processing
* SAGE - for symbolic/"exact" problems
What do you think about such specialization? Is it intentional?
P.S. I've thought on writing SAGEable Python wrapper for ALGLIB. This
idea came to me when I worked with automatically generated C# wrapper
for MPIR. It started as MPIR-related project, but now I see that the
same technology can be applied to other software projects.
I know that SAGE already has GSL wrapper, but two projects don't
overlap each other. Some functionality is present only in GSL, some -
only in ALGLIB. But is numerical analysis really needed in the SAGE?
--
With best regards,
Sergey mailto:sergey.b...@alglib.net
William Cauchois
May 5, 2010, 3:57:29 AM5/5/10
to sage-devel
On May 5, 12:42 am, Sergey Bochkanov <sergey.bochka...@alglib.net>
wrote:
the interest of the Sage community in routines for using SVMs. Just
because the Sage community in general isn't interested in a component,
however, doesn't mean that it couldn't be useful to some people.
>
> Looks like we (Open Source Community) have:
> * R - for statistical processing
> * Octave - for numerical processing
> * SAGE - for symbolic/"exact" problems
>
> What do you think about such specialization? Is it intentional?
I'm sure its intentional. Its good for a project to have both scope
and vision. However, there are circumstances in which you may want to
expand a project's scope. And SVM-Light doesn't have to be an addition
to Sage's core -- it could be an optional SPKG that interested users
may install at their leisure.
> P.S. I've thought on writing SAGEable Python wrapper for ALGLIB. This
> idea came to me when I worked with automatically generated C# wrapper
> for MPIR. It started as MPIR-related project, but now I see that the
> same technology can be applied to other software projects.
>
> I know that SAGE already has GSL wrapper, but two projects don't
> overlap each other. Some functionality is present only in GSL, some -
> only in ALGLIB. But is numerical analysis really needed in the SAGE?
>
> --
> With best regards,
> Sergey mailto:sergey.bochka...@alglib.net
In my opinion SVM functionality could be a useful addition to Sage.
For ML researchers, being able to execute a support vector machine and
then graph and manipulate the results all within an interactive
environment could be very useful. However, if no one is interested
then I won't bother expending the effort!
-- Bill
wrote:
> Hello, William.
>
> You wrote 4 мая 2010 г., 22:34:58:
>
> > Could you write a little more to sage-devel about why mathematicians
> > might care about "support vector machines" -- it's possible that most
> > people reading this have never heard of them.
>
> Being sage-devel reader for a while I may say that SAGE users are
> mostly interested in symbolic algebra, graph theory, other kinds of
> "exact algebra" (finite rings, etc.). Interest in numerical processing
> is much more lower.
You're right. I guess that's the purpose of this thread -- to gauge
>
> You wrote 4 мая 2010 г., 22:34:58:
>
> > Could you write a little more to sage-devel about why mathematicians
> > might care about "support vector machines" -- it's possible that most
> > people reading this have never heard of them.
>
> Being sage-devel reader for a while I may say that SAGE users are
> mostly interested in symbolic algebra, graph theory, other kinds of
> "exact algebra" (finite rings, etc.). Interest in numerical processing
> is much more lower.
the interest of the Sage community in routines for using SVMs. Just
because the Sage community in general isn't interested in a component,
however, doesn't mean that it couldn't be useful to some people.
>
> Looks like we (Open Source Community) have:
> * R - for statistical processing
> * Octave - for numerical processing
> * SAGE - for symbolic/"exact" problems
>
> What do you think about such specialization? Is it intentional?
and vision. However, there are circumstances in which you may want to
expand a project's scope. And SVM-Light doesn't have to be an addition
to Sage's core -- it could be an optional SPKG that interested users
may install at their leisure.
> P.S. I've thought on writing SAGEable Python wrapper for ALGLIB. This
> idea came to me when I worked with automatically generated C# wrapper
> for MPIR. It started as MPIR-related project, but now I see that the
> same technology can be applied to other software projects.
>
> I know that SAGE already has GSL wrapper, but two projects don't
> overlap each other. Some functionality is present only in GSL, some -
> only in ALGLIB. But is numerical analysis really needed in the SAGE?
>
> --
> With best regards,
In my opinion SVM functionality could be a useful addition to Sage.
For ML researchers, being able to execute a support vector machine and
then graph and manipulate the results all within an interactive
environment could be very useful. However, if no one is interested
then I won't bother expending the effort!
-- Bill
Jason Grout
May 5, 2010, 4:17:18 AM5/5/10
to sage-...@googlegroups.com
On 05/05/2010 02:57 AM, William Cauchois wrote:
>
> In my opinion SVM functionality could be a useful addition to Sage.
> For ML researchers, being able to execute a support vector machine and
> then graph and manipulate the results all within an interactive
> environment could be very useful. However, if no one is interested
> then I won't bother expending the effort!
I can see this being interesting in teaching, for example, a modeling
>
> In my opinion SVM functionality could be a useful addition to Sage.
> For ML researchers, being able to execute a support vector machine and
> then graph and manipulate the results all within an interactive
> environment could be very useful. However, if no one is interested
> then I won't bother expending the effort!
class (based on the paragraph or two that I've read about it up to this
point!) If there was an optional spkg, I'd at least install it and play
around with it for a while.
Thanks,
Jason
Harald Schilly
May 5, 2010, 6:14:18 AM5/5/10
to sage-devel
On May 5, 9:57 am, William Cauchois <wcauch...@gmail.com> wrote:
> In my opinion SVM functionality could be a useful addition to Sage.
Me too. In my opinion the optional SPKG for your binding should only
> In my opinion SVM functionality could be a useful addition to Sage.
be the first step. The ideal situation for the future is a SVM class
in the statistics section of sage, where you can pose an SVM problem
in general and then select which backend to use. Notice, that there
are already two emerging possibilities for SVMs in Sage: The first one
via R (if you install the "e1071" R package) and the second one is
part of scipy.learn: http://fseoane.net/blog/2010/plot-the-maximum-margin-hyperplane-with-scikitslearn/
In general the goal of sage is to combine such tools under a common
umbrella, just like it is currently developed for (mixed integer)
linear programming in optimization by introducing a common class to
pose such problems and a solve method, where you select the solver
engine.
H
Martin Albrecht
May 5, 2010, 6:32:52 AM5/5/10
to sage-...@googlegroups.com
Hi,
> Thanks for sharing your experiences. An optional SPKG sounds like the
> way to go. Could you point me to any resources describing how to go
> about creating an SPKG?
Have a look at:
http://www.sagemath.org/doc/developer/producing_spkgs.html
> Another thing I'm not clear on is how to
> integrate a Python C extension with Sage. There must be some SPKGs
> that do this, so maybe I could look at that source code.
Nathann's Mixed Integer Programming Solvers should be a good example. Have a
look at
cbc-2.3.p2 and glpk-4.42.p0
Cheers,
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://www.informatik.uni-bremen.de/~malb
_jab: martinr...@jabber.ccc.de
> Thanks for sharing your experiences. An optional SPKG sounds like the
> way to go. Could you point me to any resources describing how to go
> about creating an SPKG?
http://www.sagemath.org/doc/developer/producing_spkgs.html
> Another thing I'm not clear on is how to
> integrate a Python C extension with Sage. There must be some SPKGs
> that do this, so maybe I could look at that source code.
look at
cbc-2.3.p2 and glpk-4.42.p0
Cheers,
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://www.informatik.uni-bremen.de/~malb
_jab: martinr...@jabber.ccc.de
William Stein
May 5, 2010, 8:43:39 AM5/5/10
to sage-...@googlegroups.com
On Wed, May 5, 2010 at 12:42 AM, Sergey Bochkanov
<sergey.b...@alglib.net> wrote:
> Hello, William.
>
> You wrote 4 мая 2010 г., 22:34:58:
>
>> Could you write a little more to sage-devel about why mathematicians
>> might care about "support vector machines" -- it's possible that most
>> people reading this have never heard of them.
>
> Being sage-devel reader for a while I may say that SAGE users are
> mostly interested in symbolic algebra, graph theory, other kinds of
> "exact algebra" (finite rings, etc.). Interest in numerical processing
> is much more lower.
This is somewhat true, but very unfortunate. A big part of the
<sergey.b...@alglib.net> wrote:
> Hello, William.
>
> You wrote 4 мая 2010 г., 22:34:58:
>
>> Could you write a little more to sage-devel about why mathematicians
>> might care about "support vector machines" -- it's possible that most
>> people reading this have never heard of them.
>
> Being sage-devel reader for a while I may say that SAGE users are
> mostly interested in symbolic algebra, graph theory, other kinds of
> "exact algebra" (finite rings, etc.). Interest in numerical processing
> is much more lower.
"mission statement" of the Sage project is to create a viable free
open source alternative to Matlab. As such, numerical processing is
just as important as symbolics to the Sage project.
And, it's important to me too. In fact, the last major code I wrote
for Sage was a new fairly complete hidden Markov model library, which
I wrote from scratch. That's 100% numerical code.
>
> Looks like we (Open Source Community) have:
> * R - for statistical processing
> * Octave - for numerical processing
> * SAGE - for symbolic/"exact" problems
>
> What do you think about such specialization? Is it intentional?
only for symbolic/exact problems.
Note that R is part of Sage, as are numpy, scipy, cvxopt, and GSL, as
you of course know. These were all added several years ago, when we
decided that numerical computation must be a central goal of Sage.
> P.S. I've thought on writing SAGEable Python wrapper for ALGLIB. This
> idea came to me when I worked with automatically generated C# wrapper
> for MPIR. It started as MPIR-related project, but now I see that the
> same technology can be applied to other software projects.
>
> I know that SAGE already has GSL wrapper, but two projects don't
> overlap each other. Some functionality is present only in GSL, some -
> only in ALGLIB. But is numerical analysis really needed in the SAGE?
In fact, it is likely to be by far the most important part of Sage in
the long run.
William
>
> --
> With best regards,
> Sergey mailto:sergey.b...@alglib.net
>
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
William Stein
Professor of Mathematics
University of Washington
http://wstein.org
William Cauchois
May 5, 2010, 1:50:52 PM5/5/10
to sage-devel
Thanks for the help and support! I need to make PySVMLight a little
more complete and robust, and then I'll look into packaging it for
Sage.
On May 5, 5:43 am, William Stein <wst...@gmail.com> wrote:
> On Wed, May 5, 2010 at 12:42 AM, Sergey Bochkanov
>
> > Sergey mailto:sergey.bochka...@alglib.net
> University of Washingtonhttp://wstein.org
more complete and robust, and then I'll look into packaging it for
Sage.
On May 5, 5:43 am, William Stein <wst...@gmail.com> wrote:
> On Wed, May 5, 2010 at 12:42 AM, Sergey Bochkanov
>
>
> > --
> > To post to this group, send an email to sage-...@googlegroups.com
> > To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> > For more options, visit this group athttp://groups.google.com/group/sage-devel
> > --
> > To post to this group, send an email to sage-...@googlegroups.com
> > To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> University of Washingtonhttp://wstein.org
>
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group athttp://groups.google.com/group/sage-devel
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
Sergey Bochkanov
May 7, 2010, 1:55:10 AM5/7/10
to William Stein
Hello, William.
You wrote 5 мая 2010 г., 16:43:39:
> Yes, numerical analysis is definitely really, really needed in Sage.
> In fact, it is likely to be by far the most important part of Sage in
> the long run.
I think that I should look in this direction... I hope to
implement Python wrapper several months later. Making spkg from it
may be next step.
You wrote 5 мая 2010 г., 16:43:39:
> Yes, numerical analysis is definitely really, really needed in Sage.
> In fact, it is likely to be by far the most important part of Sage in
> the long run.
implement Python wrapper several months later. Making spkg from it
may be next step.
William Stein
May 7, 2010, 12:05:50 PM5/7/10
to sage-...@googlegroups.com
On Thu, May 6, 2010 at 10:55 PM, Sergey Bochkanov
<sergey.b...@alglib.net> wrote:
> Hello, William.
>
> You wrote 5 мая 2010 г., 16:43:39:
>
>> Yes, numerical analysis is definitely really, really needed in Sage.
>> In fact, it is likely to be by far the most important part of Sage in
>> the long run.
>
> I think that I should look in this direction... I hope to
> implement Python wrapper several months later. Making spkg from it
> may be next step.
Thank you!!
<sergey.b...@alglib.net> wrote:
> Hello, William.
>
> You wrote 5 мая 2010 г., 16:43:39:
>
>> Yes, numerical analysis is definitely really, really needed in Sage.
>> In fact, it is likely to be by far the most important part of Sage in
>> the long run.
>
> I think that I should look in this direction... I hope to
> implement Python wrapper several months later. Making spkg from it
> may be next step.
>
> --
> With best regards,
> Sergey mailto:sergey.b...@alglib.net
>
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
Sergey Bochkanov
May 8, 2010, 4:40:27 AM5/8/10
to William Stein
Hello, William
by the way, what do you think about using in SAGE both double and
multiple precision versions of ALGLIB?
I have fully functional multiple precision version of ALGLIB which
relies on MPFR for floating point computations. It includes multiple
precision linear algebra, solvers, interpolation, numerical
integration, optimization, FFT. It can be downloaded from
http://www.alglib.net/translator/re/alglib-2.5.0.mpfr.zip
I've contacted Octave team and proposed to use MP ALGLIB from Octave
but looks like they are more interested in keeping MATLAB
compatibility than in extension of the package functionality.
P.S. I've changed working schedule for Python wrapper project. I think
that something functional will be ready in the May.
by the way, what do you think about using in SAGE both double and
multiple precision versions of ALGLIB?
I have fully functional multiple precision version of ALGLIB which
relies on MPFR for floating point computations. It includes multiple
precision linear algebra, solvers, interpolation, numerical
integration, optimization, FFT. It can be downloaded from
http://www.alglib.net/translator/re/alglib-2.5.0.mpfr.zip
I've contacted Octave team and proposed to use MP ALGLIB from Octave
but looks like they are more interested in keeping MATLAB
compatibility than in extension of the package functionality.
P.S. I've changed working schedule for Python wrapper project. I think
that something functional will be ready in the May.
William Stein
May 8, 2010, 4:42:14 AM5/8/10
to sage-...@googlegroups.com
On Sat, May 8, 2010 at 1:40 AM, Sergey Bochkanov
<sergey.b...@alglib.net> wrote:
> Hello, William
>
> by the way, what do you think about using in SAGE both double and
> multiple precision versions of ALGLIB?
>
> I have fully functional multiple precision version of ALGLIB which
> relies on MPFR for floating point computations. It includes multiple
> precision linear algebra, solvers, interpolation, numerical
> integration, optimization, FFT. It can be downloaded from
> http://www.alglib.net/translator/re/alglib-2.5.0.mpfr.zip
My first thought is that it would be *awesome* to have _efficient_
<sergey.b...@alglib.net> wrote:
> Hello, William
>
> by the way, what do you think about using in SAGE both double and
> multiple precision versions of ALGLIB?
>
> I have fully functional multiple precision version of ALGLIB which
> relies on MPFR for floating point computations. It includes multiple
> precision linear algebra, solvers, interpolation, numerical
> integration, optimization, FFT. It can be downloaded from
> http://www.alglib.net/translator/re/alglib-2.5.0.mpfr.zip
multiprecision linear algebra, etc., in Sage.
This is the sort of thing people expect from Sage, but are often
disappointed to find that we don't have.
Very cool.
>
> I've contacted Octave team and proposed to use MP ALGLIB from Octave
> but looks like they are more interested in keeping MATLAB
> compatibility than in extension of the package functionality.
>
> P.S. I've changed working schedule for Python wrapper project. I think
> that something functional will be ready in the May.
>
> --
> With best regards,
> Sergey mailto:sergey.b...@alglib.net
>
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
Jason Grout
May 8, 2010, 11:55:03 AM5/8/10
to sage-...@googlegroups.com
On 05/08/2010 03:42 AM, William Stein wrote:
> On Sat, May 8, 2010 at 1:40 AM, Sergey Bochkanov
> <sergey.b...@alglib.net> wrote:
>> Hello, William
>>
>> by the way, what do you think about using in SAGE both double and
>> multiple precision versions of ALGLIB?
>>
>> I have fully functional multiple precision version of ALGLIB which
>> relies on MPFR for floating point computations. It includes multiple
>> precision linear algebra, solvers, interpolation, numerical
>> integration, optimization, FFT. It can be downloaded from
>> http://www.alglib.net/translator/re/alglib-2.5.0.mpfr.zip
>
> My first thought is that it would be *awesome* to have _efficient_
> multiprecision linear algebra, etc., in Sage.
> This is the sort of thing people expect from Sage, but are often
> disappointed to find that we don't have.
>
> Very cool.
Exactly my first thoughts! +1 on the idea of having good multiprecision
> On Sat, May 8, 2010 at 1:40 AM, Sergey Bochkanov
> <sergey.b...@alglib.net> wrote:
>> Hello, William
>>
>> by the way, what do you think about using in SAGE both double and
>> multiple precision versions of ALGLIB?
>>
>> I have fully functional multiple precision version of ALGLIB which
>> relies on MPFR for floating point computations. It includes multiple
>> precision linear algebra, solvers, interpolation, numerical
>> integration, optimization, FFT. It can be downloaded from
>> http://www.alglib.net/translator/re/alglib-2.5.0.mpfr.zip
>
> My first thought is that it would be *awesome* to have _efficient_
> multiprecision linear algebra, etc., in Sage.
> This is the sort of thing people expect from Sage, but are often
> disappointed to find that we don't have.
>
> Very cool.
linear algebra!
Thanks,
Jason
Sergey Bochkanov
May 8, 2010, 4:13:40 PM5/8/10
to William Stein
Hello, William.
> My first thought is that it would be *awesome* to have _efficient_
> multiprecision linear algebra, etc., in Sage.
> This is the sort of thing people expect from Sage, but are often
> disappointed to find that we don't have.
As for the efficiency, I may say that performance of the
multiple precision ALGLIB is influenced by following factors:
1. low-level assembly code for the underlying MP-arithmetics
2. algorithmic optimization of the high level code
3. OOP overhead
4. Multi-core systems support
(1) - assembly coding. ALGLIB uses MPFR which in turn relies on highly
optimized GMP/MPIR. Double precision ALGLIB, however, isn't optimized
- it is generic C, but we are talking about multiple precision
version.
(2) - algorithmic optimizations:
* Direct linear algebra algorithms (real or complex Cholesky/LU/
inversion/solvers) are as good as their LAPACKs counterparts.
* SVD/EVD, however, use suboptimal algorithms - with 3-4 times larger
FLOP counts than that of the LAPACKs. It is going to be improved, but
with no definite schedule.
* Other algorithms (numerical integration, interpolation,
optimization) are competitive with implementations from other
numerical packages.
(3) - OOP overhead. Multiple precision ALGLIB makes use of OOP to
implement multiple precision expressions like "x=y+z". However, it
leads to excessive creation of temporaries, so I will replace OOP by
something less human-readable but more efficient. It is relatively
easy to do because I use automatic translation to generate MP ALGLIB,
so I just have to make slight changes in the translator.
(4) - Multi-core systems support. ALGLIB supports only single threaded
model of computations. Multi-threading support is top-priority for me,
so things are going to improve, but without definite schedule too.
Summarizing all mentioned above, I can say that, in my opinion,
multiple precision ALGLIB is good enough to be used on moderate-sized
problems. Furthermore, in some cases (direct linear algebra on a
single-core system; integration, interpolation, optimization - any
number of cores) only marginal improvements are possible.
One thing that I need is help with multiple precision version. It is
relatively easy to implement wrapper for double precision ALGLIB, and
I can do it myself. But multiple precision version needs more: a)
multiple precision Python object, b) multiple precision
arrays/matrices, c) smooth integration of these MP objects in the SAGE
framework.
I have very little experience with Python, so it is better to find
experienced SAGE developer who wants to work with me on this project.
I can build low level "SAGE <-> MP ALGLIB" interface, but I need
someone who can help with higher level constructs and with smooth
integration in the SAGE framework.
P.S. BTW, may be it is time to make a new thread for this discussion -
something like "multiprecision SAGE"? We've gone far from the original
topic :)
> My first thought is that it would be *awesome* to have _efficient_
> multiprecision linear algebra, etc., in Sage.
> This is the sort of thing people expect from Sage, but are often
> disappointed to find that we don't have.
multiple precision ALGLIB is influenced by following factors:
1. low-level assembly code for the underlying MP-arithmetics
2. algorithmic optimization of the high level code
3. OOP overhead
4. Multi-core systems support
(1) - assembly coding. ALGLIB uses MPFR which in turn relies on highly
optimized GMP/MPIR. Double precision ALGLIB, however, isn't optimized
- it is generic C, but we are talking about multiple precision
version.
(2) - algorithmic optimizations:
* Direct linear algebra algorithms (real or complex Cholesky/LU/
inversion/solvers) are as good as their LAPACKs counterparts.
* SVD/EVD, however, use suboptimal algorithms - with 3-4 times larger
FLOP counts than that of the LAPACKs. It is going to be improved, but
with no definite schedule.
* Other algorithms (numerical integration, interpolation,
optimization) are competitive with implementations from other
numerical packages.
(3) - OOP overhead. Multiple precision ALGLIB makes use of OOP to
implement multiple precision expressions like "x=y+z". However, it
leads to excessive creation of temporaries, so I will replace OOP by
something less human-readable but more efficient. It is relatively
easy to do because I use automatic translation to generate MP ALGLIB,
so I just have to make slight changes in the translator.
(4) - Multi-core systems support. ALGLIB supports only single threaded
model of computations. Multi-threading support is top-priority for me,
so things are going to improve, but without definite schedule too.
Summarizing all mentioned above, I can say that, in my opinion,
multiple precision ALGLIB is good enough to be used on moderate-sized
problems. Furthermore, in some cases (direct linear algebra on a
single-core system; integration, interpolation, optimization - any
number of cores) only marginal improvements are possible.
One thing that I need is help with multiple precision version. It is
relatively easy to implement wrapper for double precision ALGLIB, and
I can do it myself. But multiple precision version needs more: a)
multiple precision Python object, b) multiple precision
arrays/matrices, c) smooth integration of these MP objects in the SAGE
framework.
I have very little experience with Python, so it is better to find
experienced SAGE developer who wants to work with me on this project.
I can build low level "SAGE <-> MP ALGLIB" interface, but I need
someone who can help with higher level constructs and with smooth
integration in the SAGE framework.
P.S. BTW, may be it is time to make a new thread for this discussion -
something like "multiprecision SAGE"? We've gone far from the original
topic :)
Francesco Biscani
May 8, 2010, 5:35:59 PM5/8/10
to sage-...@googlegroups.com
Hi Sergey,
On Sat, May 8, 2010 at 10:13 PM, Sergey Bochkanov
<sergey.b...@alglib.net> wrote:
> (3) - OOP overhead. Multiple precision ALGLIB makes use of OOP to
> implement multiple precision expressions like "x=y+z". However, it
> leads to excessive creation of temporaries, so I will replace OOP by
> something less human-readable but more efficient. It is relatively
> easy to do because I use automatic translation to generate MP ALGLIB,
> so I just have to make slight changes in the translator.
Just FYI, you might want to look into C++ expression templates - they
might allow you to retain the convenient notation with no overhead.
This library has some nice examples of the convenience of expression
templates:
http://eigen.tuxfamily.org/index.php?title=Main_Page
Cheers,
Francesco.
On Sat, May 8, 2010 at 10:13 PM, Sergey Bochkanov
<sergey.b...@alglib.net> wrote:
> (3) - OOP overhead. Multiple precision ALGLIB makes use of OOP to
> implement multiple precision expressions like "x=y+z". However, it
> leads to excessive creation of temporaries, so I will replace OOP by
> something less human-readable but more efficient. It is relatively
> easy to do because I use automatic translation to generate MP ALGLIB,
> so I just have to make slight changes in the translator.
might allow you to retain the convenient notation with no overhead.
This library has some nice examples of the convenience of expression
templates:
http://eigen.tuxfamily.org/index.php?title=Main_Page
Cheers,
Francesco.
Sergey Bochkanov
May 9, 2010, 4:15:17 AM5/9/10
to Francesco Biscani
Hello, Francesco.
> Just FYI, you might want to look into C++ expression templates - they
> might allow you to retain the convenient notation with no overhead.
I know about expression templates, but even with templates sometimes
creation of temporary is the only way to calculate value of a complex
expression like "x = ((a+b)*(c+d)-e)/(f+3)". Am I wrong?
ALGLIB is full of code like this.
But it is possible to generate less human-readable, but more efficient
code, which will operate with numbers stored in a stack data
structure. Code like this will be hard to read (something like
assembly code or p-code, but in C++), but, from the other side, it
should be very efficient.
> Just FYI, you might want to look into C++ expression templates - they
> might allow you to retain the convenient notation with no overhead.
creation of temporary is the only way to calculate value of a complex
expression like "x = ((a+b)*(c+d)-e)/(f+3)". Am I wrong?
ALGLIB is full of code like this.
But it is possible to generate less human-readable, but more efficient
code, which will operate with numbers stored in a stack data
structure. Code like this will be hard to read (something like
assembly code or p-code, but in C++), but, from the other side, it
should be very efficient.
Francesco Biscani
May 9, 2010, 12:06:24 PM5/9/10
to sage-...@googlegroups.com
Hi Sergey,
On Sun, May 9, 2010 at 10:15 AM, Sergey Bochkanov
<sergey.b...@alglib.net> wrote:
> Hello, Francesco.
for i in (0,size):
x[i] =((a[i] + b[i]) * (c[i] + d[i]) - e[i]) / (f[i] + 3)
(i.e., element-wise), then I'm pretty confident expression templates
could eliminate all temporaries.
Cheers,
Francesco.
On Sun, May 9, 2010 at 10:15 AM, Sergey Bochkanov
<sergey.b...@alglib.net> wrote:
> Hello, Francesco.
>
> I know about expression templates, but even with templates sometimes
> creation of temporary is the only way to calculate value of a complex
> expression like "x = ((a+b)*(c+d)-e)/(f+3)". Am I wrong?
>
> ALGLIB is full of code like this.
If the expression is to be intended like this:
> I know about expression templates, but even with templates sometimes
> creation of temporary is the only way to calculate value of a complex
> expression like "x = ((a+b)*(c+d)-e)/(f+3)". Am I wrong?
>
> ALGLIB is full of code like this.
for i in (0,size):
x[i] =((a[i] + b[i]) * (c[i] + d[i]) - e[i]) / (f[i] + 3)
(i.e., element-wise), then I'm pretty confident expression templates
could eliminate all temporaries.
Cheers,
Francesco.
Sergey Bochkanov
May 9, 2010, 1:32:48 PM5/9/10
to Francesco Biscani
Hello, Francesco.
You wrote 9 мая 2010 г., 20:06:24:
> If the expression is to be intended like this:
> for i in (0,size):
> x[i] =((a[i] + b[i]) * (c[i] + d[i]) - e[i]) / (f[i] + 3)
> (i.e., element-wise), then I'm pretty confident expression templates
> could eliminate all temporaries.
I am talking about non-vectorized form of the expression. And I can't
imagine how (a+b)*(c+d) can be calculated without temporaries :) Can
you give an example?
P.S. I was a bit incorrect when talked about "temporaries overhead".
Multiple precision linear algebra operations have very little overhead
- at most one temporary is created for entire column/row operation.
OOP issues are more significant for other subroutines (optimization,
interpolation).
You wrote 9 мая 2010 г., 20:06:24:
> If the expression is to be intended like this:
> for i in (0,size):
> x[i] =((a[i] + b[i]) * (c[i] + d[i]) - e[i]) / (f[i] + 3)
> (i.e., element-wise), then I'm pretty confident expression templates
> could eliminate all temporaries.
imagine how (a+b)*(c+d) can be calculated without temporaries :) Can
you give an example?
P.S. I was a bit incorrect when talked about "temporaries overhead".
Multiple precision linear algebra operations have very little overhead
- at most one temporary is created for entire column/row operation.
OOP issues are more significant for other subroutines (optimization,
interpolation).
Francesco Biscani
May 9, 2010, 1:47:17 PM5/9/10
to sage-...@googlegroups.com
Hi Sergey,
On Sun, May 9, 2010 at 7:32 PM, Sergey Bochkanov
<sergey.b...@alglib.net> wrote:
> I am talking about non-vectorized form of the expression. And I can't
> imagine how (a+b)*(c+d) can be calculated without temporaries :) Can
> you give an example?
My bad, for some strange reason I had assumed we were talking about
overhead resulting from temporary vectors/matrices, not from the
underlying numerical primitives :) Sorry for the noise...
Cheers,
Francesco
On Sun, May 9, 2010 at 7:32 PM, Sergey Bochkanov
<sergey.b...@alglib.net> wrote:
> I am talking about non-vectorized form of the expression. And I can't
> imagine how (a+b)*(c+d) can be calculated without temporaries :) Can
> you give an example?
overhead resulting from temporary vectors/matrices, not from the
underlying numerical primitives :) Sorry for the noise...
Cheers,
Francesco
Reply all
Reply to author
Forward
0 new messages