Slow formal derivatives

[Waldek Hebisch]

If you look at 'src/input/derham.input' you will notice comment
saying that it is quite slow for large n. I looked a bit
at this and first observation is that slowness is due to
kernel manipulations. Profile shows that almost all time goes
into kernel maniputation, mainly 'SCACHE;linearSearch'.
This is called from 'FS-;diffdiff' which is responsible for
differentiating formal derivatives. Linear search is necessary
due to the way we implement formal derivatives. But it is
actually worse: repeating the same calculation shows growing
time. Just to see scale, one of calculation in
'src/input/derham.input' is to calculate second exterior
derivative of general form in n variables. General form
involves n formal function in n variables. First exterior
derivative needs to compute n^2 partial derivatives (n functions
times n variables). Second exterior derivative needs
n(n-1)n partial derivatives. So togeter about n^3 derivatives.
For n=8 this is about 512. Even squared (due to linear search)
this does not look like very large number of operations.
However, formal derivative of order 2 contains derivatives of
order 1. And it seems that due to use of dummies we create
new kernels, so when we repeat calculation, then our cache keep
growing.

This suggest that we should re-think representation of formal
derivatives and possibly also use of dummies.

--
Waldek Hebisch

[Qian Yun]

(I have not tried to implement the following idea in FriCAS.)

I have always liked the idea presented in SICM (sister book
of SICP) Structure and Interpretation of Classical Mechanics:

https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/9579/sicm_edition_2.zip/chapter001.html

No dummy var involved. Instead view "diff" as a higher order
operator: it acts on other operator and returns a new operator.

So instead of the having new kernels (and new dummy var)
for each new argument,

(1) -> f := operator 'f

(1) f

(2) -> argument first kernels D(f(x),x)

(2) [f(%A), %A, x]

(3) -> argument first kernels D(f(x^2),x)

2
(3) [f(%B), %B, x ]



(4) -> argument first kernels D(f(x^3),x)

3
(4) [f(%C), %C, x ]

The new plan should be generating a "new operator" "%diff(f)"
and its argument are x,x^2,x^3 respectively.

This "new operator" "%diff(f)" can store the argument "f"
into its properties, I guess. And add special "%equal" for it.

- Qian

[Qian Yun]

https://github.com/oldk1331/fricas/commit/642ce7d42e4168313816ba2dd703bfa04efa4cf0

Here is a sketch implementation of this idea,
now dummyvars are gone. The new implementation
is much shorter than the old one. The nesting kernels
of high order derivatives are gone as well.

- Qian

[Qian Yun]

Hi Waldek,

This thread is almost one year old, any opinions on this?

- Qian

On 4/17/24 10:29 PM, Qian Yun wrote:
> https://github.com/oldk1331/fricas/

[Waldek Hebisch]

On Sun, Mar 02, 2025 at 05:44:47PM +0800, Qian Yun wrote:
> Hi Waldek,
>
> This thread is almost one year old, any opinions on this?
>
> - Qian
>
> On 4/17/24 10:29 PM, Qian Yun wrote:
> > https://github.com/oldk1331/fricas/
> > commit/642ce7d42e4168313816ba2dd703bfa04efa4cf0
> >
> > Here is a sketch implementation of this idea,
> > now dummyvars are gone.  The new implementation
> > is much shorter than the old one.  The nesting kernels
> > of high order derivatives are gone as well.

Sorry, Github made fetching patches harder so I did not try this
immediately and than forgot about it. I have now looked at it
and see potential problem: the patch stores information in
operator properties which makes such operators slower than
other (they must use linear search in kernel cache).

I did not look deeper, in particular there is question what
happens during substitutions ('subst' and 'eval'). Also
it seems that you generate different kernels for different
orders of derivatives, that is potentially quite expensive.

--
Waldek Hebisch