On Fri, May 17, 2024 at 10:11:18AM +0200, Ralf Hemmecke wrote:
> Dear Wakdek,
>
> your recent contribution of rsimp is not totally satisfactory to me, since
> it applies only to expressions that start with an 'nthRoot operator. It's a
> good service function, but I wanted something that also applies to
> combinations of such expression. So I wrote the following function to apply
> rsimp recursively.
>
> ZZ ==> Integer
> EXZ ==> Expression ZZ
> recursiveRootSimplification(x: EXZ): EXZ ==
> liu: Union(List EXZ, "failed") := isTimes x
> liu case List EXZ =>
> reduce(_*, [recursiveRootSimplification(z) for z in liu], 1)
> liu := isPlus x
> liu case List EXZ =>
> reduce(_+, [recursiveRootSimplification(z) for z in liu], 0)
> is?(x, 'nthRoot) =>
> r: Kernel EXZ := retract(x)@Kernel(EXZ)
> a: List EXZ := argument retract x
> ra: EXZ := recursiveRootSimplification(a.1)
> ex := if #a < 2 then sqrt(ra) else ra^(1/a.2)
> u: Union(EXZ, "failed") := rsimp(ex)$RootSimplification
> u case "failed" => ex
> u :: EXZ
> x
>
> Do you think that it makes sense to include that somewhere (where?) in
> FriCAS?
>
> I do not care much about the name except that it should have no
> abbreviation.
>
> The specification of rsimp does not say much about validity of the
> transformation, i.e. whether x and rsimp(x) are actually the same root (over
> complex numbers). Or do we have a statement in FriCAS about which of the n
> possible values of an nthRoot expression, the nthRoot expression actually
> represents.
>
> With recursive application that could lead to a completely different root
> value. Maybe that must be either said in the documentation or some numerical
> code must be added to ensure that not suddenly a different branch is chosen.
Concerning specification: 'rsimp' is working with _fields_, not
numbers. More precisely, 'rsimp' works with generators and
"field descriptors". "Field descriptor" tells you how to
build a field starting from base field (that is field of rational
numbers or field or rational functions). 'rsimp' works with
algebraic extentions of base field. Such extention is built
adding successive generators and descriptor tells you minimal
polynomial of new generator in terms of previously added
generators. 'rsimp' is supposed to produce field that is
izomorphic to input field, but has lower nesting depth.
Taking about field descriptors may be intimidating for users
and also we need an easy way to specify field descriptor.
Those two problems are solved by using expressions as field
descriptors. More presicly, 'nthRoot' specifies apropriate
field extention and simultaneously serves as generator of
this extention. There is a catch here: not all expressions
actually define fields. To define a field roots appearing in
the expression must be independent. By extention, roots
created by 'rsimp' should be independent.
Concerning exact specification, 'rsimp' tries to find
izomorphic field with description of lower nesting depth.
AFAIK there are open theoretical questions about what
exacly is possible. In particular, it seems that there
are fields which can not have description with lower nesting
depth, but which can be embedded in bigger field of lower
nesting depth. However, here detailed problem statement
matters a lot. AFAIK using my definitions problem is open.
'rsimp' is using approach which is usually called "Zippel
denesting". Again, characterizing cases when this approach
works is an open problem. I mean, one can write condtions
which must be satisfied at each step, but since 'rsimp'
transforms field descriptors in each step it is not clear
how to simply formulate needed condition in terms of input
data.
Concerning extentions: I plan to substantially extend 'rsimp'.
Some extentions look quite easy, but there is question of
specification and efficiency. Namely, "well specified"
"easy" extentions heavily use factorization which may
lead to quite long execution time. In some cases it is
possible to use cheaper methods, but that needs more code.
Having said that, as long as you do not require much
removing restriction on having single kernel looks
easy.
I consider recursive apprach like you used as completely
inappropriate. First, recursive approach tends to repeat
similar calculations, so it make efficiency problems
worse. Second, trying to handle parts of expression like
you do is likely to introduce dependent roots, which means
that we no longer have a field and leads to various
troubles.
Concerning branches: from algebraic point of view all branches
are equivalent (as long as kernels are independent). In other
words, choice of branches is extenal to 'rsimp', 'rsimp' simply
must be careful to avoid creating dependent roots. Of course,
users may use some "established" convention like principal
branch. In the future I will probably add some code to
make behaviour with such conventions better. For numbers
in principle it is possible to use numerical computations
to track branches. This may need rather large accuracy,
but other computations in 'rsimp' may be quite costly, so
probably numerical computations have acceptable cost. Still,
tracking needed accuracy requires appropriate code. Also,
from my point of view important advantage of 'rsimp' is that
it can deal with functions. But for functions principal
branch convention usually leads to troubles: one have to
spend large effort to get principal branch and frequently
this is wrong branch, so this effort is wasted.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/fricas-devel/ZkdMrsmVz1MLj01M%40fricas.org.
