[fricas-devel] Fwd: The free field in FriCAS :-)

[Bill Page]

On Fri, Sep 7, 2018 at 12:24 PM Konrad Schrempf wrote:
...
For Bill: If it helps to support further discussions, please put the
code on github (maybe including the mini-documentation). I guess that
it will take a while to include it in standard FriCAS. Just tell me if
you need a formal declaration for the distribution.

Is there something important I forgot? Some months ago I just claimed
that FriCAS will be the first computer algebra system being able to
work with elements in the universal field of fractions of a free
associative algebra. Now you can convince yourself. I guess that it
takes a while to get used to working with linear representations
(admissible linear systems). For small polynomials that really looks
like an overkill. But for the example on page 15 one could see the
beauty of Cohn's theory. You should try p_43^-1 ...

--

Documentation: https://github.com/billpage/ncpoly/blob/master/fdalg_20180907.pdf

Source code: https://github.com/billpage/ncpoly

Comments appreciated.

[Ralf Hemmecke]

Hi Konrad,

First of all, thanks to all who worked on
https://github.com/billpage/ncpoly. It's always nice to see new research
entering FriCAS.

I admit that I haven't followed the fdalg discussion very deeply, but
reading your documentation is not very helpful.

What is the audience for
https://github.com/billpage/ncpoly/blob/master/fdalg_20180907.pdf ?

Is Section 2 really relevant if I just want to compute with elements in
a free field? Wouldn't I just want to construct some (non-commutative)
polynomials and then "divide" them similar to the commutative case. I
would think that as a user I first must learn how to get the basic
things done before going into detail of how it is implemented.

Why not starting with "Let f be the non-commutative polynomial x -
x*y*x. In the following we compute its inverse f^(-1)." And then you
demonstrate how this can be done and explain how the different parts of
the output are to be interpreted.

Furthermore, I haven't seen that you ever specified that you write a dot
instead of 0 in your matrices.

The example f=(x-xyx)^(-1) (on page 2) it would certainly be helpful, if
you explained how one constructs the entries of A.
At the beginning of page 4 I then read "g_11 : FDA := x+x*y*x". Why now
+ instead of the - in f?

Only a few naive comments...

Ralf

Post by Bill Page
...
For Bill: If it helps to support further discussions, please put the
code on github (maybe including the mini-documentation). I guess that
it will take a while to include it in standard FriCAS. Just tell me if
you need a formal declaration for the distribution.
Is there something important I forgot? Some months ago I just claimed
that FriCAS will be the first computer algebra system being able to
work with elements in the universal field of fractions of a free
associative algebra. Now you can convince yourself. I guess that it
takes a while to get used to working with linear representations
(admissible linear systems). For small polynomials that really looks
like an overkill. But for the example on page 15 one could see the
beauty of Cohn's theory. You should try p_43^-1 ...
--
Documentation: https://github.com/billpage/ncpoly/blob/master/fdalg_20180907.pdf
Source code: https://github.com/billpage/ncpoly
Comments appreciated.

[Ray]

Post by Ralf Hemmecke
Hi Konrad,
First of all, thanks to all who worked on
https://github.com/billpage/ncpoly. It's always nice to see new research
entering FriCAS.
I admit that I haven't followed the fdalg discussion very deeply, but
reading your documentation is not very helpful.
What is the audience for
https://github.com/billpage/ncpoly/blob/master/fdalg_20180907.pdf ?
Is Section 2 really relevant if I just want to compute with elements in
a free field? Wouldn't I just want to construct some (non-commutative)
polynomials and then "divide" them similar to the commutative case. I
would think that as a user I first must learn how to get the basic
things done before going into detail of how it is implemented.
Why not starting with "Let f be the non-commutative polynomial x -
x*y*x. In the following we compute its inverse f^(-1)." And then you
demonstrate how this can be done and explain how the different parts of
the output are to be interpreted.
Furthermore, I haven't seen that you ever specified that you write a dot
instead of 0 in your matrices.
The example f=(x-xyx)^(-1) (on page 2) it would certainly be helpful, if
you explained how one constructs the entries of A.
At the beginning of page 4 I then read "g_11 : FDA := x+x*y*x". Why now
+ instead of the - in f?
Only a few naive comments...
Ralf

Post by Bill Page
...
For Bill: If it helps to support further discussions, please put the
code on github (maybe including the mini-documentation). I guess that
it will take a while to include it in standard FriCAS. Just tell me if
you need a formal declaration for the distribution.
Is there something important I forgot? Some months ago I just claimed
that FriCAS will be the first computer algebra system being able to
work with elements in the universal field of fractions of a free
associative algebra. Now you can convince yourself. I guess that it
takes a while to get used to working with linear representations
(admissible linear systems). For small polynomials that really looks
like an overkill. But for the example on page 15 one could see the
beauty of Cohn's theory. You should try p_43^-1 ...
--
Documentation: https://github.com/billpage/ncpoly/blob/master/fdalg_20180907.pdf
Source code: https://github.com/billpage/ncpoly
Comments appreciated.

There are two forms of factoring programs.  I have a test harness to
both; separately right now.
In order to try things out:
Using Konrad Schrempf's method you can do something like this
x19:FDA :=(z+1)*(z+2)*(x-2);  +++The declaration is not optional
factor(x19)::List(XDP)
--- Or more surprising to me, but proves there is no cheating:
aa:FDA := (x^6-1)*(x^6+1)
factor(aa)::List(XDP)
---
--- For Bill Page's solution
x19:XDP :=(z+1)*(z+2)*(x-2);  +++The declaration is not optional
factor(x19)::List(XDP)
aa:XDP :=(x^4-1)
factor(aa)::List(XDP) ; +++ The "List(XDP)" is not needed but I put it in
--- for uniformity.  The x^6-1 causes a stack error in lisp.
---           Total bytes allocated    =    1072031360
---           Dynamic-space-size bytes =    1073741824

---
I will send the git hub addresses for the testing if you want; I promise
to put up
Schrempf's test fixture on git hub today.  It has improvements in
reporting but there
is something I want to add later.
My intent was to merge the two methods in the sense that the declaration
aa:XDP :=(x^4-1)
aa:FDA :=(x^4-1)
will select which factorization algorithm to use.
Schrempf's algorithm is more extensive in theory (and in fact handles
(x^6-1) more effectively).
Page's algorithm is understandable (in fact I implemented an alternate
program using the same idea)
but has less mathematical background.  It's basically "divide and
conquer" ; but seems to work except when it doesn't.

Since there didn't seem to be interest in my doing the merge I halted on
it and started looking into
Schrempf's theory.  If anybody is interested I will go back to the
coding and update Page's test output; my work on Schrempf's testing has
certain refinements.

Ray

[Bill Page]

..
There are two forms of factoring programs. I have a test harness
to both; separately right now.
Using Konrad Schrempf's method you can do something like this
x19:FDA :=(z+1)*(z+2)*(x-2); +++The declaration is not optional
factor(x19)::List(XDP)
aa:FDA := (x^6-1)*(x^6+1)
factor(aa)::List(XDP)
---
--- For Bill Page's solution
x19:XDP :=(z+1)*(z+2)*(x-2); +++The declaration is not optional
factor(x19)::List(XDP)
aa:XDP :=(x^4-1)
factor(aa)::List(XDP) ; +++ The "List(XDP)" is not needed but I put it in
--- for uniformity. The x^6-1 causes a stack error in lisp.
--- Total bytes allocated = 1072031360
--- Dynamic-space-size bytes = 1073741824
---

Except as a short reference we should probably not use the phrase
"Bill Page's solution". According to Konrad the algorithm currently
implemented in XDPOLYF1 originates from a suggestion by Daniel
Smertnig. The original version was coded by Konrad as a "exercise". I
just improved the coding a little. Its main purpose is mostly
educational and as a potential aid in further developing/testing
Konrad's ALS work. Now that the ALS coding includes a complete
factoring implementation, the actual "production" version of XDPOLYF1
should just be re-written as a wrapper to FDALG.

Rewriting XDPOLYF1 would serve to answer some of Ralf's "usability"
comments. It is probably true however the FDALG itself could be
"cleaned up" a little to seem a less developer-oriented.

I will send the git hub addresses for the testing if you want;
I promise to put up Schrempf's test fixture on git hub today.
It has improvements in reporting but there is something I want
to add later.

I still think a comprehensive testsuite for FDALG and related domains
would be a valuable addition.

Bill Page.

[Ray]

Post by Bill Page
I still think a comprehensive testsuite for FDALG and related domains
would be a valuable addition.
Bill Page.

Try this:
https://github.com/ray-rogers/NC-FDA-testing

Constructive suggestions appreciated; or just ask for rewrite privleges.

I left a _small_ residual for dual test; ignore it.
If anybody would like a separate report file for test results, it's easy to
add.   As it is: look in test.log for closing "]]" for formatted
returns/results.
Do read README.txt
Ray