ModMonic

[Ralf Hemmecke]

Johannes,

I guess, you have implemented the ModMonic domain.

To me it looks like a good candidate for being used as the
representation domain of SimpleAlgebraicExtension.

However, where SAE uses the polynomial as its third argument, ModMonic
is pretty much mutable, i.e., the polynomial is set on demand.
I wonder what the pros and cons of such an approach are.

Couldn't ModMonic also use 3 parameters like SAE?

As can be seen from
https://github.com/fricas/fricas/blob/master/src/algebra/ffpoly.spad#L211
it would mean creating a new instance of the ModMonicDomain with every
call of reducedQPowers. Would that be the problem? Too much overhead in
creating a new domain?

That's certainly a problem if FriCAS should ever be able to use the
power of running on several CPU kernels.

Ralf

[Waldek Hebisch]

Our runtime operations on types depend on caches. Unfortunately,
global caches cause serious problems for mutiprocessors. Namely,
global caches must be consistent, wich requires locking. And
locking means that "real work" is done sequenitaly and mutiprocessing
only add overhead of coordination and deciding which CPU should
do the work. Bottom line: forget about easy programming for
mutiprocessors. You need to stick to well-thought and rigid
protocol. Basically, you need _very_ carefuly separate local
and global data and design protocols so that global data
stays consistent with minimal time spent on synchronization.
Do it in "easy way" and you either get fast, but inconsistent
system or correct dog-slow system.

AFAIK up to now all mayor CAS-es run main code in single thread.
Multithreading is used in low level libraries like BLAS, polynomial
multiplcation, etc. Low level libraries can multithread because
they do not provide niceties like "hidden" modulus, all arguments
are explicit and shared data is limited to bare necessity (basically
what is needed to decompose problem between thread and combine
back results).

Coming back to your specific question: having modulus as
parameter moves mutable data from user level to Spad runtime.
You get safer code but at some cost. Unfortunately cost
of creating domains is substantial and in multithreading
context would be _much_ higher.

Now, there is tricky balace between convenience of coding and
performance. When code is hard to write it make sense to go
for easier codning even if speed is much lower. That is
usual approach taken in most of FriCAS code. OTOH, finite
fields and finite rings are at core of fast algorithms
so we definitely want _low level_ routines dealing with
finite fields to be as fast as possible. Our finite field
machinery is at higher level, but it would make a lot of
sense to build user level finite fields on top of optimized
low level routines (which we need for fast algorithms).
With such setting ModMonic would be just convenience for
users or not needed at all, at least not needed for
finite fields.

--
Waldek Hebisch