An incremental method to compute (Abel) matrix inverses

[bo198214]

I fiddled a bit around with Gottfried's suggestion of LU decomposition of the Abel matrix (though in the end the formula is independent of the LU decomposition).

The annoying thing about calculating the intuitive Abel function (by solving the equation Ax=b where A is the Abel matrix, x the powerseries development of the Abel function and b=(1,0,...)) that if you want to increas the matrix size you have to solve the complete equation again without being able to use your previous solution.

Now I found a way how you can compute the inverse of the \( A_n \) matrix by using the \( A_{n-1} \) Abel matrix. I dissect the matrix as follows, for brevity I set \( A=A_{n-1} \):

\(
A_n=\left(\begin{array}{ccc|c}
\phantom{1}& &\phantom{1} & \\
&A& &\acute{a}\\
& & & \\\hline
&\grave{a}& &a_n
\end{array}\right)
\)

\( \acute{a} \) means column vector and \( \grave{a} \) means row vector.

The final incremental formula is then:

\( {A_n}^{-1} =(A^{-1})_{+0} + \frac{(-A^{-1}\acute{a}\oplus
1)(-\grave{a}A^{-1}\oplus 1)}{a_n-\grave{a}A^{-1}\acute{a}} \)

Where \( \oplus 1 \) means adding the entry 1 to the vector and \( (A^{-1})_{+0} \) is \( A^{-1} \) extended to a nxn matrix by filling with 0's.

The deriviation is perhaps too uninteresting and cumbersome to put, but I can post it if inquired.

[tommy1729]

what is an abel matrix ?

i know carleman and bell matrix ... whats the difference ?

maybe its the matrix equivalent of the infinite linear equations of andrews slog ...

[bo198214]

what is an abel matrix ?

i know carleman and bell matrix ... whats the difference ?

maybe its the matrix equivalent of the infinite linear equations of andrews slog ...

Oh the term was introduced by Andrew and indeed is the matrix equivalent of the infinite equation system of Andrew's slog.

Its C-I transposed (C is the infinite Carleman matrix, I the infinite identity matrix) and first column removed (which consists of only 0's) and then square truncated according to your needs of precision.

But the above inversion formula does not depend on A being an Abel matrix. It works for every invertible matrix.
But currently I see that the internal inversion algorithms of Sage are even faster to recompute the whole inverse than doing an incremtal inverse with the above formula *sigh*

[Gottfried]

I fiddled a bit around with Gottfried's suggestion of LU decomposition of the Abel matrix (though in the end the formula is independent of the LU decomposition).
(...)

Hi Henryk -

I've also tried a similar thing: to compute the new column/row of the LU-factors by the old ones - optimally by reference to the previous row/column only... without success so far.
Triggered by your msg I looked at a symbolic representation, using the symbol "u" for the log of the base (which can be substituted by 1 if the base is e = exp(1)).
So B is the Bell-matrix for x->exp(u*x), B1 is truncate(B - I) ,
Then L (lower) , D (diagonal), U (upper) the inverses of the LU-factors of B1, such if it converges, B1^-1 = U*D*L , where for the slog we need only the first column of L.
Looking at the last column of U with the idea to compose it by the previous column only (or by some composition of some earlier columns) I notice, that the entries are polynomials in u and I didn't see yet a simple possibility to determine that polynomials based on that of the previous colums. The same is true analoguously for the n'th entry in D and for the n'th row in L.

If I determine the coefficients for the powerseries for the slog by U*D*L[,0], then I see, that the degree of the polynomials, by which the coefficients are defined, increase binomially (n,2) and in our context of tetration I can't remember any recursionformula for such a situation. (In my treatize about the symbolic description of the coefficients for the dxp-Bell-matrix I came across the same growthrate of the order of the polynomials and did not find a formula how to compute one coefficient only by its index and possibly some known constants)

It would be nice to find such a formula for "the last" column in U and "last row" in L by a short recursion - this would then also allow to dismiss that matrix-inversion(s) completely... but I think, your derivation is comparably complex (so that the inversion is even faster)?

Gottfried
ah - ps: I tried also to express it in terms of (u-1) or (u+1) instead of u - but with little progress.