This Maple worksheet accompanies the paper [1]: Di Nardo E., G. Guarino, D. Senato (2011), A new algorithm for computing the multivariate Faà di Bruno’s formula, Applied Mathematics and Computation. doi:10.1016/j.amc.2011.01.001
A new algorithm for computing the multivariate Faà di Bruno’s formula
E. Di Nardo* elvira.dinardo@unibas.it http://www.unibas.it/utenti/dinardo/home.html; Tel: +39 0971205890, Fax: +39 0971205896
G. Guarino** giuseppe.guarino@aspbasilicata.it
D. Senato* domenico.senato@unibas.it
* Dipartimento di Matematica e Informatica, Università degli Studi della Basilicata, viale dell'Ateneo Lucano n.10, 85100 Potenza, Italy
**Medical School, Università del Sacro Cuore (Rome branch), Largo Agostino Gemelli n.8, 00168 Roma, Italy

Introduction


Abstract: We provide a new algorithm for computing the multivariate Faà di Bruno's formula. We follow a symbolic approach based on the classical umbral calculus that leads back the computation of the multivariate Faà di Bruno's formula to a suitable multinomial expansion. The resulting computational times are faster compared with procedures existing in the literature.
Application Areas/Subject: Combinatorics & algebraic methods
Keyword: multivariate composite function, Faà di Bruno's formula, multivariate cumulants, multivariate Hermite polynomials, classical umbral calculus.
See Also: background on the classical umbral calculus in [2], background on multiset subdivisions in [3], for different applications of multiset subdivisions see [5]


Subdivisions of a multiset


This topic has been extensively discussed in [3].
See http://www.maplesoft.com/applications/view.aspx?SID=33039 for details.
> 

> 

> 

> 

> 

> 

Examples
> 


(3.1) 
> 


(3.2) 
> 



Multivariate Faà di Bruno’s formula


A MAPLE algorithm for the computation of the multivariate Faà di Bruno’s formula by using the umbral equivalence (18) in [1].

Univariate and Multivariate Case


MFB Functions

Introduction


As we have proved in [3], the function makeTab generates a multiset subdivision (see the output of the function makeTab in the previous section).
Parameters: 2;
Univariate with Univariate
By using the subdivisions of a multiset with all equal elements, we are able to compute the univariate Faà di Bruno's formula, that is to expand
For example in order to expand we call MFB(2) which gives as output
Remark: the function MFB uses the function makeTab as we show in the following example.
Calling makeTab(2) we have The first block has two elements: its cardinality gives the index of . The second block has one element: its cardinality gives the index of . The first element in the first block has degree 1: its degree gives the index of . Since in we have two equal elements of degree 1, we get This term must be multiplied with the integer (the multiplicity) that appears in each block (for example: 1 in or n in ). The second block contains only one element with degree 2. This gives just At the end, the summation of the two terms returns .
Univariate with Multivariate
When in the multiset there are two or more different elements, the result of a call to MFB is different from the previous one. For esample MFB(1,1) generates the following output: that represents the expansion of .
Indeed if in we replace
Remark: Similarly to what it happens for the univariate/univariate case, the function MFB calls the function makeTab as we show in the following example.
Calling makeTab(1,1) we obtain
The first block has one element: its cardinality gives the index of The second block has two elements: its cardinality gives the index of . In the blocks, two variables are involved. This explains why we use two indexes in elements. In particular we have: we have , and from the block we get . At the end, the summation of the two terms returns .


Examples


Univariate with Univariate
> 


(4.1.3.1) 
> 


(4.1.3.2) 
Univariate with Multivariate
> 


(4.1.3.3) 
> 


(4.1.3.4) 
> 


(4.1.3.5) 
> 


(4.1.3.6) 



The function joint



Introduction


The procedure joint provides a way to multiply the factors of formula (22) in [1].
Parameters:
Example:
If we need to multiply MFB(1,0) with MFB(1,1) we must follow the following steps:
1) Call MFB(1,0) and
2) For each output, make the following evalutions: where i=1..n.
So from MFB(1,0) = , by using the previous evaluations, we have
From MFB(1,1) =
3) Compute the following cefficients:
in the example and
4) Multiply the two previous terms as follows:


Examples


> 


(4.2.3.1) 
> 


(4.2.3.2) 
> 


(4.2.3.3) 



The function mkT



Introduction


This procedure gives a list of all subvectors having the same lenght of a vector V and such that their summation returns V.
Parameters: mkT(V, n), n2;
Note: the output of
Example: Suppose to call mkt([1,1],2).
1) First the function makeTab is called: makeTab(1,1)=
2) From this list and for each block, we consider only the first subblock, that is
3) Since the first block has cardinality one, we set as we have asked for two blocks (that is two subvectors, note that the second parameter is n=2). So we have [1,0],[0,1]
4) The result is the list
5) At the end, in order to have all lists, we need to permute the subblocks for each block, that is:
This function is used in the master function.


Examples


> 


(4.3.3.1) 
> 


(4.3.3.2) 
> 


(4.3.3.3) 



The Master Function UMFB



Introduction


(Umbral Multivariate Fa`a di Bruno’s Formula)
All previous steps are combined in this procedure. The UMFB function recalls the MFB function for the univariate and the multivariate case (parameter n=1) and allows us to construct the multivariatemultivariate case (parameter n>1).
Parameters: UMFB(V, n), V=
Esample: UMFB([1,3],2) =
Pseudocode:
UMFB(V, n) if n = 1 then return( MFB(V) ); S := 0;
for v in mkT( V, n ) do S := S + joint(v) {with }
next for
return(S);
end:


Examples


Univariate with Univariate we have the same result of MFB function.
> 


(4.4.3.1) 
> 


(4.4.3.2) 
Univariate with Multivariate
> 


(4.4.3.3) 
> 


(4.4.3.4) 
Multivariate with Multivariate
> 


(4.4.3.5) 
> 


(4.4.3.6) 
> 


(4.4.3.7) 
> 


(4.4.3.8) 




Test Results



Introduction


In this section we analyze the accuracy of the results comparing the output obtained by using the Maple diff function (routine by which the multivariate Faà di Bruno’s formula is computable in Maple) .To this aim, we set:
In order to compare the results we have set up three functions: decoSub, deco and testUMFB.
The decoSub function is an auxiliary routine useful for the deco function. The deco function takes the result of the function UMFB as input and gives an output equal to the Maple function diff. The testUMFB function checks the accuracy of the result.
Parameter: where V, n are the same as the UMFB function and tDebug 2 {true, false} [set tDebug = true if you need to display also the output of the function diff]
Example:
+
+
+
+
+
We get the same result from
setting
;


Execution Samples


> 


(5.3.1) 
> 


(5.3.2) 
> 


(5.3.3) 
> 


(5.3.4) 
> 


(5.3.5) 
> 


(5.3.6) 
> 


(5.3.7) 



Execution Time


In this section we analize the difference of the execution time between the UMFB function and the Maple diff function.
Notice: to perform an appropriate test, make a restart (using "!!!" for recall the entire worksheet) to clear any cash areas.
> 

> 


(6.1) 


Conclusions


By using the classical umbral calculus, we provide a new Maple algorithm for computing
the multivariate Faà di Bruno's formula for the following compositions: univariate with univariate, univariate with multivariate, multivariate with univariate, multivariate with the same multivariate, multivariate with different multivariates in any arbitrary number of components. The resulting algorithm is speeder of the routine MAPLE diff performing the same computations.


References


[1] Di Nardo E., G. Guarino, D. Senato (2011), A new algorithm for computing the multivariate Faà di Bruno’s formula, Appl. Math. Comp. doi:10.1016/j.amc.2011.01.001
[2] Di Nardo, E., Senato, D. (2006) An umbral setting for cumulants and factorial moments. European J. Combin. 27, No. 3, 394–413. (http://www.arxiv.org/abs/math/0412052)
[3] Di Nardo E., G. Guarino, D. Senato, Multiset Subdivision, source Maple algorithm located in www.maplesoft.com (http://www.maplesoft.com/applications/view.aspx?SID=33039)
[4] Di Nardo E., G. Guarino, D. Senato (2008) An unifying framework for kstatistics, polykays and their generalizations. Bernoulli. Vol. 14(2), 440468. (http://www.unibas.it/utenti/dinardo/BEJ6163290408.pdf)
[5] Di Nardo E., G. Guarino, D. Senato, A Maple algorithm for kstatistics, polykays and their multivariate generalization, source Maple algorithm located in www.maplesoft.com (http://www.maplesoft.com/applications/view.aspx?SID=33040)
Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for noncommercial, nonprofit use only. Contact the author for permission if you wish to use this application in forprofit activities

