Summer of Code - abstract Algebra
Robert Schwarz
I would like to contribute to this program with some classes/
algorithms from abstract algebra. In an e-mail to Ondrej, I've already
proposed to implement Gröbner bases, with applications to multivariate
equations.
Having studied the code, I thought that it was also possible, to
implement some other arithmetic first: Perhaps finite rings/fields,
algebraic extensions to the integers or rationals together with some
factorization, including polynomials.
(I got a bit confused, by the series' leading term returning the
smallest degree term and stuff. Also, I don't want to put even more
things in the basic class, like the conjugate method for complex
numbers.)
I have to think about how long that could possibly take, it depends on
the generality of the concepts. But perhaps the typical users are not
really interested in those abstract concepts, and math students
specialising in algebra or number theory would take SAGE anyway.
Don't get me wrong, I'd love to work on this, but I hesitate to render
the program code unnecessarily complicated, for the sake of
generality, if it isn't needed/wanted.
Also, I was wondering about the general policy towards the use of
other Python modules. While I can't think of any particular exemple
now, I guess you want to keep it all self-contained? (besides modules
of the standard library)
Hope to get some feedback on that, will then prepare the application
tomorrow.
Robert
Fabian
> hi all,
>
> I would like to contribute to this program with some classes/
> algorithms from abstract algebra. In an e-mail to Ondrej, I've already
> proposed to implement Gröbner bases, with applications to multivariate
> equations.
Hi Robert. Groebner bases would be terribly useful in sympy. As you
already know, it has many applications, and there's even a variant of
the Risch algorithm (for integration) that makes use of groebner bases.
>
> Having studied the code, I thought that it was also possible, to
> implement some other arithmetic first: Perhaps finite rings/fields,
> algebraic extensions to the integers or rationals together with some
> factorization, including polynomials.
> (I got a bit confused, by the series' leading term returning the
> smallest degree term and stuff. Also, I don't want to put even more
> things in the basic class, like the conjugate method for complex
> numbers.)
Yes, we are trying to pull things out of the class Basic. I'm currently
working in the branch sympy-mathml which throws all the printing stuff
out of the core ...
>
> I have to think about how long that could possibly take, it depends on
> the generality of the concepts. But perhaps the typical users are not
> really interested in those abstract concepts, and math students
> specialising in algebra or number theory would take SAGE anyway.
I'm interested in those abstract concepts, and I'm sure they will be
implemented some day, although at this stage other issues have a greater
priority (eq solving, integration, etc.)
>
> Don't get me wrong, I'd love to work on this, but I hesitate to render
> the program code unnecessarily complicated, for the sake of
> generality, if it isn't needed/wanted.
For what i've understood, I think it all can implemented in the
sympy.modules package (say for example sympy.modules.groebner or
sympy.modules.aalgebra ...), and it wouldn't be imported by default, so
it wouldn't make the code slow, bloated or anything like that.
>
> Also, I was wondering about the general policy towards the use of
> other Python modules. While I can't think of any particular exemple
> now, I guess you want to keep it all self-contained? (besides modules
> of the standard library)
I think the general policy is something like this: (correct me Ondrej if
i'm wrong):
- the core shouldn't depend on anything beyond the python standard
library
- It's ok to have some dependencies in the modules, as long as they
are justified and are cross-platform, althought we prefer to stay
self-contained.
Ondrej Certik
your questions are very relevant and tough. When I was starting SymPy
maybe two years ago, I had no idea where it could lead to, I just
wanted to do it better. I had a goal and this still holds:
Try to find a best (python) interface to a symbolic system. Speed is
not a (top) priority.
But now as more and more things are being implemented and especially
after many discussion with Fabian and others, my idea is becoming more
and more crystallized. As Fabian correctly said:
sympy.core should be a well defined symbolic engine, self-contained,
depending only on standard python, with as much functionality taken
away (into sympy.modules) as possible, to keep it clean. there
shouldn't be any floating functions around, only several (around 7
currently) classes and all the functionality implemented using methods
and all the algorithms implemented localy to each class (to keep the
inter dependencies to minimum). The sympy.core could be possibly
rewriten in C++ in the future for speed - but having it in pure python
has also advantages and I want to leave it in python (but possibly
create a C++ implementation as an option).
sympy.modules will do the rest. Each module should have well defined
dependecies: sympy.core and possibly several other modules. Problem
here is that there are going to be functions around, like "integrate",
"limit", "ispoly" everything. Originaly I wanted to implement
everything as methods to classes, but now it's clear that modules are
needed. But even in modules we should be able to put as much
algorithms as possible into classes, like Limit, Integral, maybe a
Polynomial and then create a very few aditional functions which
normally would be as methods in sympy.core classes (mostly in Basic),
but we don't want to put them there to keep sympy.core clean and
small.
As to usage of modules beside a standard library - it is possible if
it is well-justified, but by default, sympy must run on a normal
python installation and behave nice, which means that either it
automatically switches to a slow python implementation of some
algorithm, or some functionality will be disabled by default. In any
case, the user shouldn't care (if he doesn't want) and it should just
work by itself.
As to things that belong to sympy and that not:
1) if it can be implemented as a sympy.module without changing
sympy.core (cosmetic changes to sympy.core are ok) then absolutely
yes. If the user doesn't want to use it, he will just not import the
module.
2) if it belongs to python.core, well, then it needs to be discussed,
if it is worthy the complexity.
Generaly, I don't want to reinvent a wheel. I myself can only judge
things that I understand (things in issues and the future plan) and I
think other projects are worse than SymPy in that, in terms of
simplicity. I don't personally use rings, fields and similar stuff. If
it is the case 1), then I have no objections, in the worst case you
will reinvent the wheel. If it is the case 2), then we will need to
discuss it in detail.
And I (now I am speaking for myself) as a user, don't need the
abstract stuff. Only if it would make SymPy simpler and easier to
understand, or if it would give more order to it - like the group
theory gives a nice insight into many phenomena, but in fact it
doesn't say anything new.
Fabian is working on a MathML which should keep sympy.core clean and
allow us to write modules for exporting it to other formats, for
interacting with other packages, like maple, SAGE, latex, etc. This
should also allow an easy inclusion of SymPy into SAGE in the same way
as maple is included. So keep this in mind when implementig something
that SAGE does well. On the other hand, SAGE is a huge package, but I
want to keep SymPy lightweight, at least in the default installation.
So I hope I answered all your questions. :)
Ondrej
Robert Schwarz
> > I have to think about how long that could possibly take, it depends on
> > the generality of the concepts. But perhaps the typical users are not
> > really interested in those abstract concepts, and math students
> > specialising in algebra or number theory would take SAGE anyway.
>
> I'm interested in those abstract concepts, and I'm sure they will be
> implemented some day, although at this stage other issues have a greater
> priority (eq solving, integration, etc.)
>
>
>
I'll try to give some examples. For finite rings/fields there are
always the classical applications of cryptography and error-correcting
codes. The RSA method is a straight forward example, you all probably
know. Another one would be a discrete logarithm (The multiplicative
group is cyclic, that is, all elements are a power of some generator.
Given the `index table', one can then implement multiplication of two
elements by adding there index.) One could implement things like this,
too, though I don't see a need beside education, or perhaps a
debugging help for a real crypto library. But this would be a feature,
no one expects from a general purpose CAS, isn't it?
It's the same thing for correcting-codes, where Hamming codes are an
example of a finite field (an extention of F2, the field of {0, 1}),
but not really useful for anything else than demonstration.
More generally, finite fields are useful for the factorization of
polynomials, too (even rational polynomials). If one is interested in
the factorization of a rational polynomial with integer coefficients
into his primes (in Q[X]), and the leading term is 1 (or -1), the
polynomial is irreducible iff it is irreducible over the integers.
Then, if I would have a decomposition of a polynomial p=q*r, this
would also give me decomposition modulo n, for an integer n. So, if
there is NO decomposition mod n, there can NOT be one over the
integers. Factorization over a finite field can be very simple, if the
degree is at most 3, I could just test all elements of the fields for
zeros.
Then, there is the Zassenhaus algorithm, a state-of-the-art polynomial
factorization tool, using finite fields (the proof also needs some
theory of p-adic numbers, if I remember rightly).
Tomorrow (monday), I can go to the library and look for the wonderful
(but expensive) book
http://www.amazon.com/Introduction-Finite-Fields-Applications-Revised/dp/0521460948/ref=pd_bxgy_b_text_b/002-0770645-2518422
and find some more.
For the algebraic extension, I don't remember any real `real-life'
application right now, we used it for rather theoretic purposes, and
that made me happy enough. Actually, I do a lot of computation here
(in finite fields, for example, mod p for p prime), for my math
courses, mostly number theory. Here, I prefer to test some conjecture
in the Python interpreter, first, perhaps finding some counter-
examples, before concentrating on a proof. So, for math students doing
abstract math, it would be nice to have a free, extensible plattform,
to help with homework or experiments.
Also, an `application' of a theorem or algorithm can be something very
different for a math student and programmer/user, but I don't want to
talk about the purpose of math (for now) ;-)
Hope that helped a bit. Perhaps I'll find some more, to me, the
theoretic interest is already motivation enough, so I didn't prepare
some list of nice uses.
Robert.
PS: Is there some issue with unicode characters? In the reply, I
couldn't see my Umlaut ö in Gröbner. Wenn I turned encoding to western
(ISO-8859-1) it worked for the reply, but not for my original post.
Robert Schwarz
to do that.
Implementing a `solve' method, that takes some funktion and somehow
looks for roots is no lesser `evil', than defining an ambiguous
`simplify' method.
For an equation like X^2 - 2 = 0, I could return no roots, looking for
rationals, or some sqrt(2) and -sqrt(2), or even some complex numbers,
if needed. And for returning some symbolic sqrt(2), that uses no float
representation, but still gives sqrt(2)^2 = 2 (and is an integer), I
guess we would need to introduce some extension field of the
rationals, where sqrt(2) has a sense (even if sqrt(3) has not) and
where you can compute sqrt(2) + 1 and sqrt(2) - 1 and where [sqrt(2)
+ 1]*[sqrt(2) - 1] really reduces to 3. (As you can see here, in the
ring of integers with some sqrt(2), 3 is no longer prime.)
So, even if I just implemented Gröbner bases to use them for
polynomial equations, at some point, there is a design decision.
But yes, that could all be implemented in an independent module with
separate `solve' methods.
By the way, are there any plans to implement some (numerical) Newton
method or do you rely on other Python projects?
Robert
Ondrej Certik
it belongs to the case 1) in my last email, so it's fine.
As to your particular usage - I think you might look at SAGE, I think
it's written by number theorists and cryptographers. But I would be of
course glad, if you contribute to SymPy, at least the polynomial
factorization, because this is needed. :)
When you talked about a Zassenhaus algorithm, it reminded me I read
somewhere about a Zassenhaus expansion, and maybe you could explain me
this thing:
When you take the Baker-Campbell-Hausdorff formula let's say for matrices:
exp(A)exp(B) = exp(A+B+1/2[A,B]+....)
how can I derive a similar formula for:
exp(A+B) = exp(A) exp(B) exp(const*[A,B]) exp(...)
I think I read somewhere the second formula is called a Zassenhaus
expansion, but I don't know how to prove it nor how to derive the
higher terms.
Ondrej
Ondrej Certik
> to do that.
> Implementing a `solve' method, that takes some funktion and somehow
> looks for roots is no lesser `evil', than defining an ambiguous
> `simplify' method.
>
> For an equation like X^2 - 2 = 0, I could return no roots, looking for
> rationals, or some sqrt(2) and -sqrt(2), or even some complex numbers,
> if needed. And for returning some symbolic sqrt(2), that uses no float
> representation, but still gives sqrt(2)^2 = 2 (and is an integer), I
> guess we would need to introduce some extension field of the
> rationals, where sqrt(2) has a sense (even if sqrt(3) has not) and
> where you can compute sqrt(2) + 1 and sqrt(2) - 1 and where [sqrt(2)
> + 1]*[sqrt(2) - 1] really reduces to 3. (As you can see here, in the
> ring of integers with some sqrt(2), 3 is no longer prime.)
I am not sure I understand this paragraph. If you try in isym.py:
In [1]: Rational(2).sqrt()**2
Out[1]: 2
In [2]: ((Rational(2).sqrt() +1)*(Rational(2).sqrt() -1)).expand()
Out[2]: 1
It seems to me that sqrt(2)^2 = 2 and [sqrt(2) + 1]*[sqrt(2) - 1]=1
work as expected.
You discovered a bug in the second case, but it's fixed in the svn now.
Maybe I know what you mean - you want to have some means of
distinguishing between integers, rationals and real numbers (like
sqrt(2))? I agree that currently we correctly distinguish integers and
rationals, but there is a little problem of distinguishing sqrt(2)
from a float, since isnumber() returns True for both of it. But I
think that just introducing another method would solve it. And you can
just create a parameter to the solve() function to tell it what kind
of solutions you are interested in. Not mentioning a fact, that maybe
the easiest way is to return the most general solution (complex
numbers) and you can than later test it, if it is rational, or real,
or integer, or whatever.
>
> So, even if I just implemented Gröbner bases to use them for
> polynomial equations, at some point, there is a design decision.
>
> But yes, that could all be implemented in an independent module with
> separate `solve' methods.
Wouldn't my proposed solution (above) solve the problem?
> By the way, are there any plans to implement some (numerical) Newton
> method or do you rely on other Python projects?
Well, I think scipy is good for numerical methods. There are plans for
symbolic methods, like a Gaussian elimination. Do you mean like for
numerically solving equations (and differential equations)? Right, I
think it would be nice to have a simple numerical solver in SymPy, as
a module, and optionaly use scipy for some other things.
It occured to me a nice application (I am sure it is routinely used in
Maple for example):
When solving some differential equation, I am always writing the code
from scratch, using for example some fortran runge-kutta solver, but I
need to calculate the derivatives myself, etc. But using SymPy, I
could just wrote the equation as an expression and SymPy would do the
rest. Well, but usually, I have some parameter in the ODE defined on a
grid, so it wouldn't help me much in this case.
Ondrej
Robert Schwarz
> it's written by number theorists and cryptographers. But I would be of
> course glad, if you contribute to SymPy, at least the polynomial
> factorization, because this is needed. :)
>
polynomial arithmetic? I see that you already have this item in the
issue list.
> When you talked about a Zassenhaus algorithm, it reminded me I read
> somewhere about a Zassenhaus expansion, and maybe you could explain me
> this thing:
>
> When you take the Baker-Campbell-Hausdorff formula let's say for matrices:
>
> exp(A)exp(B) = exp(A+B+1/2[A,B]+....)
>
> how can I derive a similar formula for:
>
> exp(A+B) = exp(A) exp(B) exp(const*[A,B]) exp(...)
>
> I think I read somewhere the second formula is called a Zassenhaus
> expansion, but I don't know how to prove it nor how to derive the
> higher terms.
>
I'm sorry, I don't know an answer now, and I don't think that this is
related to the Zassenhaus algorithm for factorization. But the
Wikipedia of matrix exponentiation is interesting, I'll think about
that tomorrow in the Métro (I'm in Paris, at the moment).
So, there is also a need for symbolic linear algebra? When reading
about matrix exponentiation, I was reminded of the Jordan normal form,
a really nice result, but needs polynomial factorization, too.
Here, at Université Denis Diderot (Paris7) I still have courses and
also some exams, but who knows, perhaps on some day next week, I feel
the urge to think about polynomial representations and play a bit with
your code. It's the best way to see how much time is needed for
planning and implementation of some other project related to it.
Robert
PS: Do we all share the same time zone? This normally poses some
problems (or speed advantage?) in international teams of developers,
but I think in this case, phone calls or VoIP would be possible, for
some discussion.
PPS: Did you know of Inkscape's integrated `shared whiteboard'? You
can use it to share all of Inkscapes drawing facilities, using a SVG
file, communicating with a group over jabber. When looking for an app
like that, I only found very old solutions, and wanted to take a look
at Inkscape, to experiment with Input/Drawing, et voilà. Already
working product (with some issues on windows, though). A great way to
talk about science, if you are not in the same room.
> >http://www.amazon.com/Introduction-Finite-Fields-Applications-Revised...
> > and find some more.
>
> > For the algebraic extension, I don't remember any real `real-life'
> > application right now, we used it for rather theoretic purposes, and
> > that made me happy enough. Actually, I do a lot of computation here
> > (in finite fields, for example, mod p for p prime), for my math
> > courses, mostly number theory. Here, I prefer to test some conjecture
> > in the Python interpreter, first, perhaps finding some counter-
> > examples, before concentrating on a proof. So, for math students doing
> > abstract math, it would be nice to have a free, extensible plattform,
> > to help with homework or experiments.
> > Also, an `application' of a theorem or algorithm can be something very
> > different for a math student and programmer/user, but I don't want to
> > talk about the purpose of math (for now) ;-)
>
> > Hope that helped a bit. Perhaps I'll find some more, to me, the
> > theoretic interest is already motivation enough, so I didn't prepare
> > some list of nice uses.
>
> > Robert.
>
> > PS: Is there some issue with unicode characters? In the reply, I
> > couldn't see my Umlaut ? in Gr?bner. Wenn I turned encoding to western
Robert Schwarz
On Mar 19, 2:21 am, "Ondrej Certik" <ond...@certik.cz> wrote:
I'm sorry, I got that totally wrong ( 2-1=1 NOT 3).
There is another case, if you have I=sqrt(-1) joined to your integers,
then you have (1+I)(1-I)=1+1=2 so that 2 loses primality.
Similary, if I take a=sqrt(-2) to my integers (ring extension) I have
(1+a)(1-a)=1-a**2=1-(-2)=3.
It is already getting late, and the tea is cold ;-)
Anyway, in this case, the computations with simple roots like sqrt(2)
is quite easy to handle, as opposed to an/the abstract root of some
other polynomial P, for example some root of unity, scaled, and added
to another one. Here, the arithmetic is determined by addition and
multiplication in the polynomial ring Q[X]/P, which is a field, for P
prime (irreducible).
But I have to admit that I did not look at the source code in all
detail, I'll hopefully make up for that
tomorrow (after writing the application, finally).
>
> > So, even if I just implemented Gröbner bases to use them for
> > polynomial equations, at some point, there is a design decision.
>
> > But yes, that could all be implemented in an independent module with
> > separate `solve' methods.
>
> Wouldn't my proposed solution (above) solve the problem?
>
Yeah, I guess so. An optional parameter to the solve method is easier
and equally flexible as separate methods.
> > By the way, are there any plans to implement some (numerical) Newton
> > method or do you rely on other Python projects?
>
> Well, I think scipy is good for numerical methods. There are plans for
> symbolic methods, like a Gaussian elimination. Do you mean like for
> numerically solving equations (and differential equations)? Right, I
> think it would be nice to have a simple numerical solver in SymPy, as
> a module, and optionaly use scipy for some other things.
>
> It occured to me a nice application (I am sure it is routinely used in
> Maple for example):
>
> When solving some differential equation, I am always writing the code
> from scratch, using for example some fortran runge-kutta solver, but I
> need to calculate the derivatives myself, etc. But using SymPy, I
> could just wrote the equation as an expression and SymPy would do the
> rest. Well, but usually, I have some parameter in the ODE defined on a
> grid, so it wouldn't help me much in this case.
>
>
In maple, there is some fool-proof pop-up window, where you fill in
the equations and then select symbolic/numerical solution and then the
actual algorithm.
We implemented those runge-kutta solvers, too, in C/C++ and Matlab, in
a lecture about ODEs, but I don't use them on a day-to-day basis.
Prime factorizations and quadratic residues are much more common,
theses days.
For some other application of abstract algebra (or pure mathematics,
in general) I found a nice project on
http://www.mathematik.uni-dortmund.de/CoCoA/en/Project/index.html
even if I don't know the direct uses of all the theories mentioned in
the list. But CoCoA (and Singular) might be an important inspiration,
when thinking about the representation of solutions in terms of the
polynomials that define them.
Ondrej Certik
Of course. Symbolic matrices are already implemented, but the linear
algebra (determinants, eigenvalues, elimination, diagonal or Jordan
form, exponentiation...) is still missing.
> PS: Do we all share the same time zone? This normally poses some
> problems (or speed advantage?) in international teams of developers,
> but I think in this case, phone calls or VoIP would be possible, for
> some discussion.
>
> PPS: Did you know of Inkscape's integrated `shared whiteboard'? You
> can use it to share all of Inkscapes drawing facilities, using a SVG
> file, communicating with a group over jabber. When looking for an app
> like that, I only found very old solutions, and wanted to take a look
> at Inkscape, to experiment with Input/Drawing, et voilà. Already
> working product (with some issues on windows, though). A great way to
> talk about science, if you are not in the same room.
I didn't know about it. It looks cool. You mean like to use it to draw
mathematical formulas?
Robert Schwarz
> > PPS: Did you know of Inkscape's integrated `shared whiteboard'? You
> > can use it to share all of Inkscapes drawing facilities, using a SVG
> > file, communicating with a group over jabber. When looking for an app
> > like that, I only found very old solutions, and wanted to take a look
> > at Inkscape, to experiment with Input/Drawing, et voilà. Already
> > working product (with some issues on windows, though). A great way to
> > talk about science, if you are not in the same room.
>
> I didn't know about it. It looks cool. You mean like to use it to draw
> mathematical formulas?
Yeah, that too, but rather chemical structure formulae, or drawings of
some bizarre surfaces and graphs and stuff. The advantage of Inkscape
is the SVG, so that you can easily save and display the result. There
is also undo/redo functionality and nice colors and anti-aliasing...
So, I went to the library today and found that book on finite fields.
Nice memories came up, but it didn't provide any non-theoretic
applications besides crypto and coding. So instead, I looked for
something different and got me
http://www.cs.amherst.edu/~dac/iva.html
It looks very nice and even has a list of `student projects' with
references to algorithms in the book.
>From what I remember/understand, finding the roots of a polynomial in
one variable over the complex/real/rational/integer numbers is not at
all trivial and often relies on the factorization over finite fields.
So I guess this is not really an optimal goal for a SoC project,
because it is likely to fail with unexpected complexity.
Fortunately, the computation of Gröbner bases only uses gcd, lcm,
division and other basic operations of polynomials, and could be done
for the rationals first, then generalized later. The application of
Gröbner bases (or resultants) to multivariate polynomial equations
consists mainly of elimination of the variables and then reducing the
number of equations, so that this could be done idependently to the
final step of solving the single resulting equation.
The implentation of other fields/rings with polynomial factorization
could then be announced as a future idea or bonus, if there is still a
lot of time.
I also thought about the matrix exponantiation, it comes all down to
computing (x+y)^n.
Normaly, one would use the binomial formula, which depends on xy=yx,
so there is some defect, that looks like (xy-yx) for n=2. This can be
rewritten as exp of something, similary to log, but I failed to deduce
some general formula. Do you really need this?
Time for dinner and CV...
Robert
Ondrej Certik
> It looks very nice and even has a list of `student projects' with
> references to algorithms in the book.
This looks good. It seems you just need to take the maple sources and
translate them to SymPy.
> I also thought about the matrix exponantiation, it comes all down to
> computing (x+y)^n.
> Normaly, one would use the binomial formula, which depends on xy=yx,
> so there is some defect, that looks like (xy-yx) for n=2. This can be
> rewritten as exp of something, similary to log, but I failed to deduce
> some general formula. Do you really need this?
Not now, but it is useful. I'll do it, when I need it. You just need
to decompose the matrix into the form SDS^-1, where D is diagonal (if
that is possible) and then just do:
exp (SDS^-1) = S exp(D) S^-1
and computing exp(D) is trivial, just exponentiate things on the diagonal.
If we only want to take into account algebraic properties of the
noncommutative symbols, then we cannot use this procedure, but anyway,
you don't have bother with that.
Ondrej
Robert Schwarz
> >http://www.cs.amherst.edu/~dac/iva.html
> > It looks very nice and even has a list of `student projects' with
> > references to algorithms in the book.
>
> This looks good. It seems you just need to take the maple sources and
> translate them to SymPy.
>
But the book is a great resource of examples, and pseudocode.
I finally finished the application, hope it is not to long/general.
Feel free to give some feedback, but don't waste your time with
details ;-)
Perhaps I forgot something important:
(personal data will be added)
------------------------------------------
Project Title:
SymPy: Multivariate Polynomial Equations and Gröbner Bases
Synopsis:
Extend SymPy to handle basic polynomial methods.
Implement Gröbner bases (with Buchberger's algorithm).
Use Gröbner bases for elimination in polynomial equations.
Optional: Factorization of polynomials, using different fields.
Benefits for the Python and mathematics/science community:
The SymPy package is a lightweight and easy-to-use CAS, build up
from scratch in Python. As such, it has several advantages to
other software packages. For educational purposes, students can
easily study the algorithms without struggling with syntax or
technical details. The full power of the `real' programming
language encourages experimenting and prototyping new
ideas. Compared to SAGE, a collection of rather sophisticated,
specialized packages, SymPy is a good opportunity for students to
explore the world of symbolic computation.
While the calculus specific operations like integration and
differentials form a great part of the source base, some more work
in the domain of abstract algebra is needed. The Gröbner bases can
be used in many different algorithms and have direct applications
solving multivariate polynomial equations. Besides the
implementation of the basis generating algorithm, more general
methods are needed, like the computation of the greatest common
divisor, division of polynomials and different monomial orders
(lex, grad-lex, ...).
If the time permits, general (non-trivial) factorization
algorithms can be added, making use of finite fields or algebraic
extensions to the rational numbers. Here, different
representations are needed for different purposes: symbolic
(anonymous) roots of irreducible polynomials, real/complex
numbers, perhaps decomposed in radicals, as in
x = sqrt(2/3) - i*sqrt(1/3)
Future ideas can be discussed and then developed independently.
Preliminary (generous) plan:
Weeks -8 to 2:
Get familiar with the source base,
discuss possible representations,
look for articles/books describing the needed algorithms
(for example http://www.cs.amherst.edu/~dac/iva.html)
compare solutions of other software packages:
SAGE, Singular, Macaulay etc.
Week 2, 3:
Develop basic (multivariate) polynomial handling:
GCD, LCM (extended Euclid's algorithm)
division algorithm,
different monomial orders (lex, rev lex, grad lex).
perhaps also some ideal methods
(is polynomial P in the ideal gen. by <F, G, H ...>?)
Week 5, 6:
Implement Buchberger's algorithm to generate a Gröbner base,
given a list of polynomials with rational coefficients.
Week 7:
Handle multiple multivariate polynomial equations,
implement resultants and discriminants for elimination purposes.
Week 8, 9:
Use the computed Gröbner base for elimination of the equations,
prepare the final step of factorization/root finding.
Week 10, 11:
Think about the representation of different rings/fields and
their arithmetic.
Try some factorization algorithms (Berlekamp, Zassenhaus)
Last days:
Clean up all code,
fill in missing tests,
complete documentation.
curriculum vitae:
Robert Schwarz was born on 4th April 1985 in Stuttgart, Germany.
After visiting different schools in Heidelberg and Eggenfelden, he
graduates 2004 with the German Abitur. In the same year, Robert
Schwarz begins his studies of mathematics and computer science at
the University of Heidelberg
(http://www.uni-heidelberg.de/index_e.html)
Lectures in abstract algebra and number theory were of great
interest to him. In spring 2006, he passes all pre-diploma
examinations with excellent degrees. Currently, Robert Schwarz
attends the University Paris 7
(http://www.univ-paris-diderot.fr/index.php), participating in the
ERASMUS student exchange program.
He obtained basic knowledge of programming techniques in computer
science courses, using C/C++, and lectures in applied mathematics,
implementing algorithms in Matlab. Furthermore, experience was
gained in several academic internships:
Development of a physical model of a front-wheel steered car, for
use in the MUSCOD optimization environment. Later, construction of
a prototype, using LEGO Mindstorm and direct motor controls,
resulting from the optimization software.
http://www.iwr.uni-heidelberg.de/~agbock/RESEARCH/muscod.php
3 independent projects in the division of Medical and Biological
Informatics at DKFZ (German Cancer Research Center):
http://www.dkfz-heidelberg.de/en/mbi/index.html
http://mbi.dkfz-heidelberg.de/mitk/
Template creator for new functionalities in the MITK toolkit (open
source project), using Java and a small GUI plus a plug-in for the
Eclipse IDE. Each time, new files were built, automatically
filling in names in lists, concerning Qt or CMake, for example.
Planning of a new interaction model, using hierarchical state
machines, allowing unlimited undo/redo functionality. Mouse and
keyboard controls could be given new meanings dynamically,
depending of the hierarchy of the objects dealt with. (A selected
Point belongs to a polygon, belongs to a surface, sitting in some
3D render window etc.)
Implementation of different algorithms for pose estimation (with
and without feature point correspondences). That is, given a 3D
model and 2D camera data, calculating the rotation and translation
of the camera, relative to the 3D model coordinates. (C++)
Python is my language of choice for everyday needs. Its versatility
enabled me to use it for the vast majority of common scripting issues
-- curiously, it also turned out to be an efficient calculator
replacement.
This project gives me an opportunity to deepen my knowledge in the
context of a clear, modular system, and applying my theoretical
understanding in abstract algebra to useful algorithms.
In case of further questions do feel free to contact me.
Kind regards,
Robert Schwarz
Ondrej Certik
> > translate them to SymPy.
> >
> Well, maple sources are not really easy to `take', are they?
> But the book is a great resource of examples, and pseudocode.
Well, I implemented limits using a code for maple. It is basically a
line by line translation. Only a very few things had to be done
differently. The difference between an algorithm in a book and an
actual implementation (doesn't matter it's for maple) is enormous.
Ondrej
Fabian
> Week 5, 6:
> Implement Buchberger's algorithm to generate a Gröbner base,
> given a list of polynomials with rational coefficients.
maybe you could also consider implementing the new faugere f 4 algorithm
(http:/magma.maths.usyd.edu.au/users/allan/gb/faugere_f4.ps.gz )
instead/ in addition to the buchberger one, since i've heard that it is
usually much faster
Robert Schwarz
On Mar 20, 8:34 am, Fabian <fab...@fseoane.net> wrote:
> > Week 5, 6:
> > Implement Buchberger's algorithm to generate a Gr?bner base,
> > given a list of polynomials with rational coefficients.
>
> maybe you could also consider implementing the new faugere f 4 algorithm
> (http:/magma.maths.usyd.edu.au/users/allan/gb/faugere_f4.ps.gz )
> instead/ in addition to the buchberger one, since i've heard that it is
> usually much faster
>
Yeah, I've heard about this algorithm, but we didn't discuss it in our
lecture (we actually did Buchberger's manually, even in the exam). If
it doesn't use some other techniques, it shouldn't take much time.
I won't (can't) change the application though, it is not really fixed
in every detail, anyway.
Robert