preparing to create new Polynomial Factoring module using MathPiper/Yacas programming language
Sherm Ostrowsky
The current polynomial factoring functions in MathPiper are partly taken directly from the corresponding Yacas functions, or slightly modified from them, or were completely replaced (sometimes successfully, sometimes not very successfully) by new ones. Some of the newest functions made use of the JAS (Java Algebra System) library. While this library contains some sophisticated stuff, and continues to be supported and improved by its creator, Heinz Kredel, we have discovered that its inclusion adds a lot of bulk to the MathPiper package, making it too large for the use to which we would like to put it. Algorithms which used JAS will be replaced with native code. This is no reflection on JAS, but rather a consequence of the current goals of the MathPiper project.
I have recently amassed a collection of several dozen of the most important articles on factorization of univariate and multivariate polynomials, and am continuing to add to it. I have read these papers, and several books which have sizable sections about this subject, a couple of times. Each time I gain a slightly better understanding of what I have to do.
For univariate polynomials, I intend to implement the by-now almost "standard" process consisting of
- square-free factorization
- distinct-degree factorization via "baby-step, giant-step" (Kaltofen and Shoup)
- equal-degree factorization (probably using Cantor-Zassenhaus algorithm)
Factorization of multivariate polynomials is an active area of study, with a considerable number of relatively new ideas. And they mostly start with a univariate solution of some kind. We already have in MathPiper a function which converts a homogeneous bivariate polynomial into a univariate one, solves the latter, then reconverts the solution for the bivariate case. Similar processes work for more general multivariate polynomials. So the univariate solution is just the beginning.
Finally, I would like to point out that the Yacas developers created and included "a simple factorization algorithm for univariate polynomials" (described in an essay with that title), which they claimed to be a new and improved version of the procedure used by others. It may very well be so. However, it apparently doesn't always work. Either the concept or the implementation was was flawed somewhere. I intend to examine this and try to either verify the correctness of the algorithm, or fix it if it has problems, and then re-implement it and see what we can find out.
I have written this note to the group in the hope of eliciting comments, ideas, and suggestions from any readers who may have knowledge which can help us to get these things done.
Sherm Ostrowsky
grzesiek
On Wednesday, September 21, 2011 6:17:11 AM UTC+2, shermo wrote:
However, it apparently doesn't always work.
Ted Kosan
> suggestions from any readers who may have knowledge which can
> help us to get these things done.
In the past we have talked about adding "assume" capabilities to
MathPiper and maybe this would be a good time to do that if you need
it for these new factoring functions.
If so, a good place to start would be for us to study how other CAS's
implement assumptions. Here is a link to the CAS Rosetta stone:
http://www.univ-orleans.fr/EXT/ASTEX/astex/doc/en/rosetta/htmla/roseta.htm
And here is a link to documentation on Sage's Assume function:
Do you think that having assumption capabilities in MathPiper would be
helpful for the functions you will be creating?
Ted
Sherm Ostrowsky
But when I tried out the function Factor() (or Factors()), using a large selection of random univariate polynomials designed to be factorable over the integers, I was surprised to discover that some of them were not successfully factored. I tried to examine the primary functions used in this attempt, BinaryFactors() and its subsidiary Fct(), I found them too complicated for me to understand. All I knew was that they sometimes failed.
So, because I could not really fix them, I decided to incorporate them into a larger algorithm which was intended to complete the factorization when they had not done so.
I may have also made minor modifications to the functions themselves, though I can't remember doing so and probably would have not tried to fix what I didn't understand.
Anyhow, the current factoring module in MathPiper is still fundamentally based on BinaryFactors(). And it definitely failed a significant number of my tests. I have not yet gone back to try to find this test suite, but it is probably still on one of my computers somewhere. I will soon be trying to revisit this stuff. But if you want to try your hand at it, I enthusiastically welcome your support! Just make a program to generate factorable univariate polynomials, and try it yourself. Let me (and the group) know what happens, please!
Sherm
Sherm Ostrowsky
I have looked at the way several different CAS handle problems involving polynomials (not just factoring). It seems to be universally done, that they DECLARE variables which are going to be used in polynomials, often with the name of the Field or Ring to which the variables belong. This appears, to me, to be a kind of "assume", but it probably has additional functionality as well. In addition, I suppose that any parameters (i.e., constants) used in the polynomial definition(s) must also belong to the same Ring or Field, though these are not always declared along with the variables.
It is not clear to me, yet, when or if these declarations "expire" and let the symbols return to ordinary life. These, and probably many other issues, will need to be clarified. But we will assuredly find that such a capability is useful for other purposes as well.
So, by all means, let's go do it.
Sherm
Sherm Ostrowsky
I have been experimenting with the Yacas algorithm embodied in the function BinaryFactors(). I can't say that I really comprehend it, but I have begun to grasp some of what it is assuming, in order to do its work. Treating the function as a Black Box, and feeding it various inputs, I have made an observation which seems to hold up, and which MIGHT go a way toward explaining why and where their algorithm breaks down.
For some reason not yet clear, but I think it may be related to their use of the Monic character of the functions they work on, their algorithm seems to want all the Square-Free factors to be LINEAR. I have found that if all the square-free factors are linear, the algorithm works flawlessly. If a single quadratic irreducible factor is appended, the algorithm seems to be able to deal with that, too. I suspect this is because it can find all the linear factors, and then just divides out to find the quadratic one.
But if TWO irreducible quadratic factors are appended, it fails to factor JUST THAT PART.
I am attaching a file that shows part of the investigation referred to.
If this turns out to be true, then I can see two possible ways to try fixing the algorithm. One would be to somehow add the capability to find quadratic factors directly. The other way would be to try factoring over ZZ, where ALL factors are linear!
That's as far as I have reached so far. Comments?
Sherm
Sherm Ostrowsky
I have a bit more to say on this subject, now. This is especially directed at grzesiek.
I have been experimenting with the Yacas algorithm embodied in the function BinaryFactors(). I can't say that I really comprehend it, but I have begun to grasp some of what it is assuming, in order to do its work. Treating the function as a Black Box, and feeding it various inputs, I have made an observation which seems to hold up, and which MIGHT go a way toward explaining why and where their algorithm breaks down.
For some reason not yet clear, but I think it may be related to their use of the Monic character of the functions they work on, their algorithm seems to want all the Square-Free factors to be LINEAR. I have found that if all the square-free factors are linear, the algorithm works flawlessly. If a single quadratic irreducible factor is appended, the algorithm seems to be able to deal with that, too. I suspect this is because it can find all the linear factors, and then just divides out to find the quadratic one.
But if TWO irreducible quadratic factors are appended, it fails to factor JUST THAT PART.
I am attaching a file that shows part of the investigation referred to.
If this turns out to be true, then I can see two possible ways to try fixing the algorithm. One would be to somehow add the capability to find quadratic factors directly. The other way would be to try factoring over ZZ, where ALL factors are linear!
WHOOPS! That "ZZ"" should be "CC" of course!
Ted Kosan
> I have looked at the way several different CAS handle problems involving
> polynomials (not just factoring). It seems to be universally done, that
> they DECLARE variables which are going to be used in polynomials, often with
> the name of the Field or Ring to which the variables belong. This appears,
> to me, to be a kind of "assume", but it probably has additional
> functionality as well. In addition, I suppose that any parameters (i.e.,
> constants) used in the polynomial definition(s) must also belong to the same
> Ring or Field, though these are not always declared along with the
> variables.
>
> It is not clear to me, yet, when or if these declarations "expire" and let
> the symbols return to ordinary life. These, and probably many other issues,
> will need to be clarified. But we will assuredly find that such a
> capability is useful for other purposes as well.
>
> So, by all means, let's go do it.
I am currently in the process of trying to fix a major bug in the
JavaScript version of MPReduce that the Khan Academy developers
uncovered and after I am done fixing it I will start studying how
other CASs implement assuming/declaring variables.
As part of this "adjusting the behavior of variables" process I would
like to change MathPiper so that using a variable name that has not
been declared would throw an exception. The reason for this is that
for the past three weeks I have been observing my students using the
experimental version of MathPiper that throws an exception if an
undefined function is called and it has resulted in a _significantly_
improved user experience. A simple function name misspelling error
that would often take 5-30 minutes to figure out is now identified
immediately.
Currently, a similar problem exists when students misspell a variable
name and create an unbound variable by accident which often causes a
program to fail in subtle and difficult to identify ways. Throwing an
exception when an unbound variable that has not been declared would
also result in a much better user experience.
Ted
grzesiek
On Saturday, September 24, 2011 2:01:50 AM UTC+2, shermo wrote:
I have a bit more to say on this subject, now. This is especially directed at grzesiek.
I have been experimenting with the Yacas algorithm embodied in the function BinaryFactors(). I can't say that I really comprehend it, but I have begun to grasp some of what it is assuming, in order to do its work. Treating the function as a Black Box, and feeding it various inputs, I have made an observation which seems to hold up, and which MIGHT go a way toward explaining why and where their algorithm breaks down.
For some reason not yet clear, but I think it may be related to their use of the Monic character of the functions they work on, their algorithm seems to want all the Square-Free factors to be LINEAR. I have found that if all the square-free factors are linear, the algorithm works flawlessly. If a single quadratic irreducible factor is appended, the algorithm seems to be able to deal with that, too. I suspect this is because it can find all the linear factors, and then just divides out to find the quadratic one.
But if TWO irreducible quadratic factors are appended, it fails to factor JUST THAT PART.
grzesiek
On Friday, September 23, 2011 6:14:06 AM UTC+2, shermo wrote:
I agree.
I have looked at the way several different CAS handle problems involving polynomials (not just factoring). It seems to be universally done, that they DECLARE variables which are going to be used in polynomials, often with the name of the Field or Ring to which the variables belong. This appears, to me, to be a kind of "assume", but it probably has additional functionality as well. In addition, I suppose that any parameters (i.e., constants) used in the polynomial definition(s) must also belong to the same Ring or Field, though these are not always declared along with the variables.
So, by all means, let's go do it.
Sherm Ostrowsky
Once again we reinvent the wheel! I recall how many problems arose in Basic programming (a LONG time ago) with undeclared variables and misspellings. As soon as variable declaration (albeit OPTIONAL, then) was introduced, these problems went away. And so most modern languages require variables to be declared.
Can you see any downside to requiring variable declarations? I can see only one, and it is actually a virtue: it requires the programmer to think ahead of time about what s/he is doing! What an imposition! Discourages spontaneity, it does!
But, getting back to the main issue of factoring polynomials, we may want to draw a distinction (as SAGE seems to do) between declaring a variable FOR ITS NAME, and declaring it FOR ITS RING/FIELD. I don't know whether this is a useful separation of categories or not.
Sherm
Sherm Ostrowsky
Sherm
Sherm Ostrowsky
We seem to be making progress, now. I don't know if fixing this particular algorithm is worth the trouble, but it seems to be a useful exercise and we will learn a lot in the process.
The alternative would be to ignore this (rather nice!) algorithm and just implement the standard three-stage factoring algorithm used be almost every other CAS. Not worrying about efficiency or speed, for now. I think MathPiper is primarily a tool for teaching and learning, and doesn't need to be particularly fast.
There are lots of more recent approaches in the literature, too, but I feel it would be premature to consider them now.
Sherm
grzesiek
On Saturday, September 24, 2011 8:08:28 PM UTC+2, shermo wrote:
Good point!
Once again we reinvent the wheel! I recall how many problems arose in Basic programming (a LONG time ago) with undeclared variables and misspellings. As soon as variable declaration (albeit OPTIONAL, then) was introduced, these problems went away. And so most modern languages require variables to be declared.
Can you see any downside to requiring variable declarations? I can see only one, and it is actually a virtue: it requires the programmer to think ahead of time about what s/he is doing! What an imposition! Discourages spontaneity, it does!
But, getting back to the main issue of factoring polynomials, we may want to draw a distinction (as SAGE seems to do) between declaring a variable FOR ITS NAME, and declaring it FOR ITS RING/FIELD. I don't know whether this is a useful separation of categories or not.
Sherm Ostrowsky
OK. We seem agreed on one thing: that declaration of variables in order to specify RING/FIELD is probably necessary and is almost universal in CASs. And Python too (see PyLab)!
As for declarations to avoid errors due to misspellings, perhaps we could have a "student" mode which does this, and an "expert" mode which does not. Or would that just be too darn complicated?
Sherm
Sherm Ostrowsky
Your argument here is pretty convincing. But Ted's observations, as a teacher USING MathPiper in classroom settings, has a lot of weight, too.
OK. We seem agreed on one thing: that declaration of variables in order to specify RING/FIELD is probably necessary and is almost universal in CASs. And Python too (see PyLab)!
WHOOPS! I meant SymPy here.
Sherm Ostrowsky
Now, I see a possibility to go beyond, by a sort-of brute-force approach as follows.
After BinaryFactors returns, check all factors found, for degree. There should be at most one factor with degree > 1.
If the degree of this polynomial is 2, then we already have the single irreducible quadratic factor. Done.
If the degree is > 2, it has to be an even number. Perhaps, check just to be sure.
Take this last polynomial and find its square-free factorization. If this has the same degree as the input polynomial, then there is only one quadratic factor, with a multiplicity which is now obvious.
In any case, try to determine how many quadratic factors are present, and of what multiplicities. Any information that can be gleaned is useful.
From here, at the moment, I have thought only in terms of nibbling strategies. For example, if we know that there is only one quadratic, say, of multiplicity 2, then a brute-force attack using this knowledge may be able to determine its coefficients (using a general quadratic ansatz).
If we know there are exactly two, each with multiplicity 1, I think a similar ansatz can find the coefficients.
Beyond this point, I have not yet thought.
Any comments?
Sherm
Sherm Ostrowsky
Sherm
Sherm Ostrowsky
I now think this: when writing functions and procedures, declarations are usually in Local() statements, and there they serve BOTH purposes! If a user wants to use Global variables, for quick and dirty calculations, then he can work without declarations. But I can tell you that I NEVER write functions and procedures with any global variables in them unless I can see no other way of accomplishing what I want to do. And this is very rare. So in practice, I am already declaring all local variables in functions, and that is what Ted wants, I think. Making it mandatory doesn't seem like such a big step in that context.
Is Grzesiek saying that he doesn't want to have to declare Local variables in functions? It seems to me that the alternative would be to have all variables in functions be global, and that is a regression to prehistoric programming practice. Or am I missing something significant here?
Sherm
Ted Kosan
> But
> there are some
> properties which are assumed to always hold. And I'd rather not be bothered
> to telling that each
> and every time. Another, related issue is how CASes are often (perhaps even
> typically) used.
> What I mean is that most often I do not think of programming but rather
> trying whether a computer
> is able to assist me with tedious but otherwise not very complicated
> calculations. This is primarily
> interactive, highly non-linear trial and error procedure. And I want to be
> able to communicate my
> intents as quickly and possible. In a way I treat the CAS as a co-worker who
> knows enough to
> avoid asking for all the details. And the more information I have to pass,
> the less useful the CAS
> is.
The kind of variables that are causing misspelling problems are what
we are currently calling unbound variables. With bound variables, the
type information is held in the value that is bound to the variable
and so bound variables will not need to be declared.
However, unbound variables will need to be declared and Sage's var
function provides a good example of an approach to declaring them
which might work well in MathPiper:
--------------------------------------
sage: x = var('x')
sage: solve(x^2 + 3*x + 2, x)
[x == -2, x == -1]
You can solve equations for one variable in terms of others:
sage: x, b, c = var('x b c')
sage: solve([x^2 + b*x + c == 0],x)
[x == -1/2*b - 1/2*sqrt(b^2 - 4*c), x == -1/2*b + 1/2*sqrt(b^2 - 4*c)]
You can also solve for several variables:
sage: x, y = var('x, y')
sage: solve([x+y==6, x-y==4], x, y)
[[x == 5, y == 1]]
sage: var('x y p q')
(x, y, p, q)
sage: eq1 = p+q==9
sage: eq2 = q*y+p*x==-6
sage: eq3 = q*y^2+p*x^2==24
sage: solve([eq1,eq2,eq3,p==1],p,q,x,y)
[[p == 1, q == 8, x == -4/3*sqrt(10) - 2/3, y == 1/6*sqrt(2)*sqrt(5) - 2/3],
[p == 1, q == 8, x == 4/3*sqrt(10) - 2/3, y == -1/6*sqrt(2)*sqrt(5) - 2/3]]
------------------------------------
For a CAS, Sage has a relatively large user base and the fact that it
requires unbound variables to be declared before they are used does
not appear to be a significant problem for its users.
> And for some reason all the popular CASes (Mathematica, Maple, Maxima)
> do not require
> predeclaration of neither functions nor variables.
None of these CASs are listed in the top 100 languages either:
http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html
After observing many of my students almost driven to tears over the
past few years because of the subtle errors caused by misspelling
function and variable names, I think that one likely reason that these
CASs are not listed in the TIOBE list is because their design of
allowing undeclared functions and unbound variables to be used makes
them too frustrating to be used by beginners.
> And turning
> mathpiper into a strongly
> typed CAS would require redesigning and rewriting it from scratch.
Adding the ability to assign type information to unbound variables is
probably going to take some work, but I think that taking the Sage
approach of declaring "unbound" variables by binding a special data
structure to them might not be too difficult to achieve in MathPiper.
For example, unbound variables currently return themselves when
evaluated and this is done by special evaluation logic which is in
LispExpressionEvaluator.java:
In> Unbind(x)
Result: True
In> Bound?(x)
Result: False
In> Solve(x^2 + 3*x + 2,x)
Result: {x==(-1),x==(-2)}
However, if an unbound variable is bound to itself, it evaluates to
itself using the normal evaluation logic (which is also in
LispExpressionEvaluator.java) and functions which require unbound
variables (such as Solve and Factor) still appear to work properly:
In> x := x
Result: x
In> Bound?(x)
Result: True
In> Solve(x^2 + 3*x + 2,x)
Result: {x==(-1),x==(-2)}
In> Factor(2*x^3 + 3*x^2 - 1)
Result: 2*(x-1/2)*(x+1)^2
Since the only people who are currently using the mathpiper2 code are
my classes, I am going to experiment with changing the evaluation
logic so that when an unbound variable is used without "declaring" it
first using this simple mechanism, an exception is thrown. This will
provide us with additional information to discuss and it should also
provide my students with a less frustrating user experience.
Sherm wrote:
>As for declarations to avoid errors due to misspellings, perhaps we could have a "student"
>mode which does this, and an "expert" mode which does not. Or would that just be too darn complicated?
This may be relatively easy to implement and it also may make sense to
do. The main issue I see with this approach is that all of the scripts
in the library which use unbound variables will still need to include
unbound variable declaration code so that they will work in student
mode.
Ted
grzesiek
Ted Kosan
> Perhaps I'm wrong, but isn't that required because sage keeps python
> as the implementation language?
All Sage code goes through a pre-parser that in theory could be used
to create a more convenient syntax for declaring variables. However,
they have chosen to use their pre-parser sparingly.
> 1. Not knowing anything about size of their user base, I'll guess that it
> does not compare to either of the 3Ms
They don't know how large their user base is either (because the don't
have a good way to measure it), but here are the Sage project's
website statistics from 2010:
http://groups.google.com/group/sage-marketing/browse_thread/thread/1011310f3d052ba1
>> None of these CASs are listed in the top 100 languages either:
>>
>> http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html
> Perhaps because they are not (at least primarily) meant to be
> programming languages? That's why I make the clear distinction
> between programming languages and CASes. I use both quite
> extensively, and the usage patterns are completely disparate.
My goal is to get millions of programmers to start using a CAS and my
main strategy for achieving this is to follow Sage's lead and make a
CAS that can be used equally well as a programming language and as a
CAS. If someone just wants an open source traditional CAS, why not
just use Maxima or Reduce?
> That's not what I meant by "strongly typed CAS"; an example of a strongly
> typed CAS is Axiom. The pre-declaration does not make a strongly-typed
> system.
Does Sage's more advanced pre-declaration capabilities qualify as
strongly-typed from your point of view?:
http://www.sagemath.org/doc/tutorial/tour_polynomial.html
http://www.sagemath.org/doc/reference/sage/rings/fraction_field.html
>> The main issue I see with this approach is that all of the scripts
>> in the library which use unbound variables will still need to include
>> unbound variable declaration code so that they will work in student
>> mode.
> Actually, this is the only benefit I can see in the pre-declaration
> requirement. It does perfectly applies to library procedures, but not
> to the routine computer-aided symbolic transformations.
What do you think about Sherm's idea of enabling the user to turn
pre-declaration of unbound variables checking on and off?
Ted
grzesiek
On Monday, September 26, 2011 3:09:10 AM UTC+2, shermo wrote:
Is Grzesiek saying that he doesn't want to have to declare Local variables in functions? It seems to me that the alternative would be to have all variables in functions be global, and that is a regression to prehistoric programming practice. Or am I missing something significant here?