1. Multivariate Polynomial Factoring Algorithm
Hello,
Has anyone seen something like this around?
I would prefer something in English, worded as
a pseudo language rather than an actual piece of
code in some language.
I have one in Lisp, but i dont know that language.
Extra credit: one that is deterministic in nature 
(circa 2004)
but i'll settle for almost anything for now.
Quick simple example:
factor: a^2+2*a*b+b^2
however there will be many more variables than just 'a' and 'b'
and many more terms also.
Thanks for any ideas or leads.
Take care,
Al
E boa sorte com sua programacao Euphoria!
My bumper sticker: "I brake for LED's"
From "Black Knight":
"I can live with losing the good fight,
but i can not live without fighting it".
"Well on second thought, maybe not."
2. Re: Multivariate Polynomial Factoring Algorithm
Hi again,
None?
I was going to update my Scientific calculator again and i wanted to
include multivariate polynomial factoring, thus i need to convert
any algorithm found into Euphoria code.
Here's an example from real life where the equation came about from
a real physical system...
H(s)=
(A*B*b^2*c*d*s^2*v+A*b^2*c*s*v+A*b^2*d*s*v+B*b*c*d*s*v+b*c*v+b*d*v)
/(A^2*B*a*b^2*c*d*s^3+A^2*a*b^2*c*s^2+2*A*B*a*b*c*d*s^2+A*B*b^2*c*d*s^2
+2*A*a*b*c*s+A*b^2*c*s+B*a*c*d*s+B*b*c*d*s+a*c+b*c)
A close look shows a few vars easily factored out, but knowing where
the equation came from says that there are only two poles, so that
means the highest power of s in the denominator is going to be s^2,
not s^3 as in the above. This means there is definitely at least
one smaller polynomial that divides perfectly into both the top and
bottom of this equation.
I have other heuristics available too because i know the physical system
where the equation came from, and this will be true for many other
equations too, but i want to eliminate that prerequisite and have an
algorithm that can handle any poly, regardless of where it came from.
It has to either factor it or else declare that it can not be reduced
at all.
Thanks in advance.
Al Getz wrote:
>
> Hello,
>
>
> Has anyone seen something like this around?
> I would prefer something in English, worded as
> a pseudo language rather than an actual piece of
> code in some language.
> I have one in Lisp, but i dont know that language.
>
> Extra credit: one that is deterministic in nature (circa 2004)
> but i'll settle for almost anything for now.
>
> Quick simple example:
> factor: a^2+2*a*b+b^2
> however there will be many more variables than just 'a' and 'b'
> and many more terms also.
>
>
> Thanks for any ideas or leads.
>
>
> Al
>
> E boa sorte com sua programacao Euphoria!
>
>
> My bumper sticker: "I brake for LED's"
>
Take care,
Al
E boa sorte com sua programacao Euphoria!
My bumper sticker: "I brake for LED's"
From "Black Knight":
"I can live with losing the good fight,
but i can not live without fighting it".
"Well on second thought, maybe not."
3. Re: Multivariate Polynomial Factoring Algorithm
Al Getz wrote:
>
> Hi again,
>
>
> None?
>
> I was going to update my Scientific calculator again and i wanted to
> include multivariate polynomial factoring, thus i need to convert
> any algorithm found into Euphoria code.
>
>
> Here's an example from real life where the equation came about from
> a real physical system...
>
> H(s)=
> (A*B*b^2*c*d*s^2*v+A*b^2*c*s*v+A*b^2*d*s*v+B*b*c*d*s*v+b*c*v+b*d*v)
> /(A^2*B*a*b^2*c*d*s^3+A^2*a*b^2*c*s^2+2*A*B*a*b*c*d*s^2+A*B*b^2*c*d*s^2
> +2*A*a*b*c*s+A*b^2*c*s+B*a*c*d*s+B*b*c*d*s+a*c+b*c)
>
> A close look shows a few vars easily factored out, but knowing where
> the equation came from says that there are only two poles, so that
> means the highest power of s in the denominator is going to be s^2,
> not s^3 as in the above. This means there is definitely at least
> one smaller polynomial that divides perfectly into both the top and
> bottom of this equation.
> I have other heuristics available too because i know the physical system
> where the equation came from, and this will be true for many other
> equations too, but i want to eliminate that prerequisite and have an
> algorithm that can handle any poly, regardless of where it came from.
> It has to either factor it or else declare that it can not be reduced
> at all.
>
> Thanks in advance.
>
>
> Al Getz wrote:
> >
> > Hello,
> >
> >
> > Has anyone seen something like this around?
> > I would prefer something in English, worded as
> > a pseudo language rather than an actual piece of
> > code in some language.
> > I have one in Lisp, but i dont know that language.
> >
> > Extra credit: one that is deterministic in nature (circa 2004)
> > but i'll settle for almost anything for now.
> >
> > Quick simple example:
> > factor: a^2+2*a*b+b^2
> > however there will be many more variables than just 'a' and 'b'
> > and many more terms also.
> >
> >
> > Thanks for any ideas or leads.
> >
> >
> > Al
> >
> > E boa sorte com sua programacao Euphoria!
> >
> >
> > My bumper sticker: "I brake for LED's"
> >
>
> Al
>
> E boa sorte com sua programacao Euphoria!
>
>
> My bumper sticker: "I brake for LED's"
>
I assume you wish to factor things with rational or integer coefficients. Then a
good paper with detailed algorithms can be found here:
http://citeseer.ist.psu.edu/cache/papers/cs/26184/http:zSzzSzwww.cs.utexas.eduzSzftpzSzpubzSztechreportszSztr73-11.pdf/musser73multivariate.pdf
I didn't find it to require much prior knowledge, apart from basic algebraic
notions, like what is a ring or a primitive element in a ring. Beware: what you
are asking for isn't a straightforward result to achieve.
CChris
4. Re: Multivariate Polynomial Factoring Algorithm
Al Getz wrote:
>
> Hi again,
>
>
> None?
>
> I was going to update my Scientific calculator again and i wanted to
> include multivariate polynomial factoring, thus i need to convert
> any algorithm found into Euphoria code.
>
>
> Here's an example from real life where the equation came about from
> a real physical system...
>
> H(s)=
> (A*B*b^2*c*d*s^2*v+A*b^2*c*s*v+A*b^2*d*s*v+B*b*c*d*s*v+b*c*v+b*d*v)
> /(A^2*B*a*b^2*c*d*s^3+A^2*a*b^2*c*s^2+2*A*B*a*b*c*d*s^2+A*B*b^2*c*d*s^2
> +2*A*a*b*c*s+A*b^2*c*s+B*a*c*d*s+B*b*c*d*s+a*c+b*c)
>
> A close look shows a few vars easily factored out, but knowing where
> the equation came from says that there are only two poles, so that
> means the highest power of s in the denominator is going to be s^2,
> not s^3 as in the above. This means there is definitely at least
> one smaller polynomial that divides perfectly into both the top and
> bottom of this equation.
> I have other heuristics available too because i know the physical system
> where the equation came from, and this will be true for many other
> equations too, but i want to eliminate that prerequisite and have an
> algorithm that can handle any poly, regardless of where it came from.
> It has to either factor it or else declare that it can not be reduced
> at all.
>
> Thanks in advance.
>
>
> Al Getz wrote:
> >
> > Hello,
> >
> >
> > Has anyone seen something like this around?
> > I would prefer something in English, worded as
> > a pseudo language rather than an actual piece of
> > code in some language.
> > I have one in Lisp, but i dont know that language.
> >
> > Extra credit: one that is deterministic in nature (circa 2004)
> > but i'll settle for almost anything for now.
> >
> > Quick simple example:
> > factor: a^2+2*a*b+b^2
> > however there will be many more variables than just 'a' and 'b'
> > and many more terms also.
> >
> >
> > Thanks for any ideas or leads.
> >
> >
> > Al
> >
> > E boa sorte com sua programacao Euphoria!
> >
> >
> > My bumper sticker: "I brake for LED's"
> >
Al:
Build a DLL with another programming langauge like Fortran and call
it from Euphoria
.
Bernie
My files in archive:
WMOTOR, XMOTOR, W32ENGIN, MIXEDLIB, EU_ENGIN, WIN32ERU, WIN32API
Can be downloaded here:
http://www.rapideuphoria.com/cgi-bin/asearch.exu?dos=on&win=on&lnx=on&gen=on&keywords=bernie+ryan
5. Re: Multivariate Polynomial Factoring Algorithm
Hi Chris,
Ok thanks, i'll take a look at that paper. At least it's something
to start with, although as you said it doesnt look very straightfoward.
I might need something a little more algorithmic in nature so i dont
have to do too much additional work.
Take care,
Al
E boa sorte com sua programacao Euphoria!
My bumper sticker: "I brake for LED's"
From "Black Knight":
"I can live with losing the good fight,
but i can not live without fighting it".
"Well on second thought, maybe not."
6. Re: Multivariate Polynomial Factoring Algorithm
Hi Bernie,
Well the problem is that right now i dont have an algorithm to be able
to build anything, DLL or program, in any language except Lisp and i
dont have too much info about Lisp and not sure i want to get involved
with that language at all.
Take care,
Al
E boa sorte com sua programacao Euphoria!
My bumper sticker: "I brake for LED's"
From "Black Knight":
"I can live with losing the good fight,
but i can not live without fighting it".
"Well on second thought, maybe not."
7. Re: Multivariate Polynomial Factoring Algorithm
Al Getz wrote:
>
> Hi Bernie,
>
>
> Well the problem is that right now i dont have an algorithm to be able
> to build anything, DLL or program, in any language except Lisp and i
> dont have too much info about Lisp and not sure i want to get involved
> with that language at all.
Al:
Try this link maybe this will help.
http://www.seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/theory.html
Bernie
My files in archive:
WMOTOR, XMOTOR, W32ENGIN, MIXEDLIB, EU_ENGIN, WIN32ERU, WIN32API
Can be downloaded here:
http://www.rapideuphoria.com/cgi-bin/asearch.exu?dos=on&win=on&lnx=on&gen=on&keywords=bernie+ryan
8. Re: Multivariate Polynomial Factoring Algorithm
Hi Bernie,
That all looks like monovariate stuff. Im after the multivariate
version. i really wanted an algorithm too, not really a bunch
of theory
Take care,
Al
E boa sorte com sua programacao Euphoria!
My bumper sticker: "I brake for LED's"
From "Black Knight":
"I can live with losing the good fight,
but i can not live without fighting it".
"Well on second thought, maybe not."
9. Re: Multivariate Polynomial Factoring Algorithm
- Posted by Bernie Ryan <xotron at ?luefrog.?om>
Jan 13, 2008
-
Last edited Jan 14, 2008
Al Getz wrote:
>
>
> Hi Bernie,
>
> That all looks like monovariate stuff. Im after the multivariate
> version. i really wanted an algorithm too, not really a bunch
> of theory
Al:
yacas -- Yet Another Computer Algebra System
At this link it talks about multivariate Algorithm near the top of page:
http://homepage.mac.com/yacas/manual/Algo.html#c1s2
http://yacas.sourceforge.net/Algomanual.html
This a link to the home page:
http://yacas.sourceforge.net/homepage.html
Bernie
My files in archive:
WMOTOR, XMOTOR, W32ENGIN, MIXEDLIB, EU_ENGIN, WIN32ERU, WIN32API
Can be downloaded here:
http://www.rapideuphoria.com/cgi-bin/asearch.exu?dos=on&win=on&lnx=on&gen=on&keywords=bernie+ryan
10. Re: Multivariate Polynomial Factoring Algorithm
- Posted by Al Getz <Xaxo at ?ol.c?m>
Jan 13, 2008
-
Last edited Jan 14, 2008
Hi Bernie,
Thanks very much for the links. They seem to have avoided the
multivariate factoring however. They talk about implementing
multivariate polynomials themselves, but i already have that
part of it implemented in the Euphoria language, as sequences
of course with a suitable structure. Now what i need is
information about actually doing the factoring, given you've
already got the poly stored and ready to be worked on using
basic math operations like add, subtract, multiply and divide,
or of course picking out parts of the poly for examination
or whatever is needed.
I still found some interesting stuff in one of those links
though, and i'll probably use that stuff too. Now all i need
is mv factoring
Take care,
Al
E boa sorte com sua programacao Euphoria!
My bumper sticker: "I brake for LED's"
From "Black Knight":
"I can live with losing the good fight,
but i can not live without fighting it".
"Well on second thought, maybe not."
