A note on computation of the slog

[Gottfried]

Notes on Andy's slog

In this note I'm proposing a method for an improvement for the computation of the slog. I've seen the thread "exact values for slog", but this exposition introduces then the need of a fixpoint, and in turn then the problem of complex series for bases b>eta. The idea which I propose here works with the original slog-matrix.

The problem with the slog-matrix as given in Andrew's papers is, that the resulting coefficients differ if the matrixsize is increased. Fortunately the values stabilize with increasing matrixsize and we can assume a convergence to the unknown values in the limit; but the unpredictability would be unsatisfactory for me.

If we introduce LU-decomposition of the slog-matrix, we have much better control over the characteristics of this change of values.

I'll reformulate Andrew's matrix-equation, which determines the slog-coefficients, a bit, to have it compatible with the usual Carleman-matrix-notation for exp().
Assume for a base b the (transposed) carleman-matrix Bb, such that

V(x)~ * Bb = V(b^x)~

then a simple reformulation of Andrew's definition for the slog-coefficients in a vector L is

I_0 = (Bb - I)*L

where I_0 is the first column of the identity matrix or simply[1,0,0,...], thus the solution were the first column of the inverse of (Bb - I) if that were invertible, and we had for the slog

V(x)~ * L = slog(x)

But because the first column in (Bb-I) is zero, such an inversion can't be made. Andrew's solution for this subproblem is, to use the top square submatrix when the empty column is removed. A nice consequence is that the first entry of L is then arbitrary in the solution and can be used for norming (It's set to -1 actually).

Let's call the so-constructed matrix B@. We don't have immediately the exact solution for the inverse in the infinite case, but may find a reasonable approximate by increasing the size nxn of B@ and observe, when the results converge to approximately constant values.

But this can be solved more elegantly using the LU-decomposition of the squarematrix B@.

Assume B@ = Q * R~ where Q and R are lower triangular. The entries of Q and R are constant if the size is changed, increasing size just appends rows and columns. The same is true for their inverses; we have

B@^-1 = R~ ^-1 * Q^-1 = RI~ * QI // give them names

The sought solution L is then

RI~ * QI * I_0 = RI~ * QI_0 = L@

just the matrixproduct of the inverse RI~ with the first column in the inverse QI and L is the concatenation

L = concat([-1], L@ )

This construction provides constant values in RI and QI for any dimension; the effect of the varying size is cought by the use of more or less columns in RI~ and rows in LI.

Thus we can compute RI and LI for a fixed size nxn, say n=64 and have the approximation of the coefficients in L by truncation of simple series instead of the untractable variability of matrix-entries which occurs by matrixinversion at varying sizes.

------------------

So far we have not yet new results, just a reformulation of the original problem. Chosing a certain size nxn gives the same answer as in the original solution of the problem.
However, we have now the entries of L as dotproducts of simple vectors, which have exact entries up to the selected size. Here "exact" means, they have the same value, which they would have in the case of infinite size.

I give the following table as an example. Assume the base b=exp(1) then we get for LI_0 (first column) and RI (columns from the second on)

Code:

´
         1.0000000  |         1.0000000                0               0               0               0              0
        0.0         |       -0.50000000       0.50000000               0               0               0              0
       -0.50000000  |        0.15384615      -0.46153846      0.30769231               0               0              0
       0.076923077  |               0.0       0.20000000     -0.40000000      0.20000000               0              0
        0.27179487  |      -0.020389669    -0.0054372451      0.22496602     -0.33167195      0.13253285              0
      -0.086939284  |     0.00012042981     -0.035406365    -0.019047982      0.23230911     -0.26657139    0.088596200
       -0.15299303  |      0.0069743952     0.0022932696    -0.046983888    -0.038118259      0.22566918    -0.20933515
       0.077898378  |    -0.00018812928      0.014141223    0.0085747395    -0.052251358    -0.057990267     0.20911611
       0.085566478  |     -0.0034592295    -0.0015275952     0.020752200     0.018548138    -0.050328489   -0.074882892
      -0.063615701  |     0.00022812262    -0.0077001833   -0.0054463926     0.024338659     0.029821927   -0.042173652
      -0.046087535  |      0.0021133242     0.0012705459    -0.012019852    -0.012043192     0.023457542    0.039689298
       0.049178756  |    -0.00025860250     0.0049910021    0.0041901657    -0.014532465    -0.019874732    0.018122626
       0.022972558  |     -0.0014743682    -0.0011845282    0.0080807452    0.0091994372    -0.013852550   -0.026895975
      -0.036530832  |     0.00028774669    -0.0036160948   -0.0036252025    0.0098790317     0.015286734  -0.0096891402

such that for the k'th entry of L we have the dot-product of the first column with the k'th column. So L[0] is set due to norming to -1, L[1] is the dotproduct of the first and the second column, as many rows as the selected matrix-size indicates.
Here I give the terms of the dotproducts, meaning columns 2 to 7 of the above table (begin counting at 1) where the coefficients of column 1 are already multiplied in:

Code:

´
             1.0000000                    .                   .                   .                    .                    .
                   0.0            0.0                         .                   .                    .                    .
          -0.076923077           0.23076923         -0.15384615                   .                    .                    .
                   0.0          0.015384615        -0.030769231         0.015384615                    .                    .
         -0.0055418075        -0.0014778153         0.061144610        -0.090146736          0.036021749                    .
       -0.000010470082         0.0030782041        0.0016560179        -0.020196788          0.023175526        -0.0077024902
         -0.0010670339       -0.00035085428        0.0071882074        0.0058318281         -0.034525812          0.032026819
       -0.000014654966         0.0011015784       0.00066795830       -0.0040702960        -0.0045173477          0.016289806
        -0.00029599408       -0.00013071094        0.0017756926        0.0015870988        -0.0043064316        -0.0064074653
       -0.000014512180        0.00048985255       0.00034647608       -0.0015483209        -0.0018971428         0.0026829064
       -0.000097397906      -0.000058556330       0.00055396535       0.00055504102        -0.0010811003        -0.0018291819
       -0.000012717749        0.00024545128       0.00020606714      -0.00071468858       -0.00097741460        0.00089124820
       -0.000033870009      -0.000027211642       0.00018563539       0.00021133461       -0.00031822851       -0.00061786934
       -0.000010511626        0.00013209895       0.00013243166      -0.00036088925       -0.00055843711        0.00035395235

and to find the values for L based on a selected dimension n we have to compute the partial sums just up to the n'th row

Code:

´
   1.0000000               .            .             .            .              .
   1.0000000             0.0            .             .            .              .
  0.92307692      0.23076923  -0.15384615             .            .              .
  0.92307692      0.24615385  -0.18461538   0.015384615            .              .
  0.91753512      0.24467603  -0.12347077  -0.074762121  0.036021749              .
  0.91752465      0.24775423  -0.12181476  -0.094958908  0.059197275  -0.0077024902
  0.91645761      0.24740338  -0.11462655  -0.089127080  0.024671463    0.024324329
  0.91644296      0.24850496  -0.11395859  -0.093197376  0.020154115    0.040614135
  0.91614696      0.24837425  -0.11218290  -0.091610277  0.015847684    0.034206669
  0.91613245      0.24886410  -0.11183642  -0.093158598  0.013950541    0.036889576
  0.91603505      0.24880554  -0.11128246  -0.092603557  0.012869441    0.035060394
  0.91602233      0.24905100  -0.11107639  -0.093318246  0.011892026    0.035951642
  0.91598846      0.24902378  -0.11089075  -0.093106911  0.011573797    0.035333773
  0.91597795      0.24915588  -0.11075832  -0.093467801  0.011015360    0.035687725

and we see, how the coefficients approximate certain values with increasing n.
(compare this values with that at http://tetration.itgo.com/pdf/TetrationS..._28-32.pdf; at the derivatives given there you need division by the appropriate factorial, so the value 0.24915 here is related to 0.49870.. from D^2 for base e, n=60 there by division by 2! and so on)
Well, so far this gives at least a bit more control over the error-estimate.

---

Now for two modifications of evaluation.
I expected, that at this stage the convergence-acceleration using Euler-summation instead of simple partial sums would come into play. But the series seems to be not well suited for Euler-summation, so this idea fails here. (Maybe there is another method available).

The second possible modification is change of order of summation.
What we have is

Code:

´
   RI~ * QI_0 = L@

and with L = concat([-1],L@) we had

Code:

´
  V(x)~ * L = slog(x)

So we can rewrite

Code:

´
  -1 + x*V(x)~ * RI~ * QI_0  = slog(x)       // where x*V(x)~ = [x,x^2,x^3,...]

Her QI_0 is only one column, and we could separate it into one column-vector of 1 and a diagonalvector

Code:

´
  -1 + x*V(x)~ * RI~ * diag(QI_0) * V(1)  = slog(x)

and arrive at a column-scaled version of RI~ (means also: rowscaled version of RI); let's call it SLOG (which is actually the matrix given in the second table above)

Code:

´
   SLOG = RI ~ * diag(QI_0)  
  -1 + x*V(x)~ * SLOG * V(1)  = slog(x)

SLOG is upper-triangular; and still has exact entries, meaning: the entries would be the same, if everything were done with infinite dimension
Then the left multiplication gives exact values in a vector, too:

Code:

´
   x*V(x)~ * SLOG  = SL(x) ~

and the unavoidable error due to truncation to finite size occurs only in the final dot-product

Code:

´  
  -1 + SL(x)~ * V(1) = slog(x)

is far better controllable and possibly reducible by some acceleration-procedure.

[bo198214]

This is ingenious!
So we have for each coefficient two sequences, where for each the n+1-th element can be computed only from the previous n elements, and the coefficient is the scalar product of both sequences.
Perhaps we can solve the convergence problem with this decomposition.

[Gottfried]

This is ingenious!

So we have for each coefficient two sequences, where for each the n+1-th element can be computed only from the previous n elements, and the coefficient is the scalar product of both sequences.
Perhaps we can solve the convergence problem with this decomposition.

Yes, that would be good!

I'm tinkering a bit with the problem (but not yet seriously): why is that series so misconfigured for convergence-acceleration with Euler/Cesaro-sum? Is there some quantity, which far-away coefficients "have to compensate" so they cannot decrease to zero (something similar to a carry in the core addition- or multiplication-procedures in a processor)?

We see, that the constant value for the series is -1, which is the expected value for the slog at x=0, and which gives a good rationale for this setting.
But what, if we could rearrange the problem around the initial condition, that we had a constant value of -2, for log_b(0)? Perhaps we would get a series which behaves nicer...
Well, I observe, that this alludes to the "nice serie"-msgs in the other thread, where we indeed deal with the "-2" -constant.
Hmm... I even don't have an idea how to access such a change...

---

Well, let's first carry home the fruits from the current results. Any further improvement can be attempted later.

[Gottfried]

One more note about a thing, which is ringing a bell.

The basic definition of the slog derives from the (impossible) inverse (Bb - I)^-1

This expression - for scalar arguments - is just the formula for the geometric series; and if Bb did not have the eigenvalue 1 we could develop the expression into the geometric series of Bb and from this into the iteration-series of b^^0+b^^1+...+b^^h+... .

Incidentally my first interesting connection with tetration was the other formula for the geometric series; that for the alternating geometric series (Bb + I)^-1 , which can be inverted and gives, for the convergent cases (all eigenvalues in Bb<=1 ) the alternating powertowerseries, about which I wrote my first small discussion (and which I call now "iteration-series" for more generality)
Surprisingly it came out, that much likely it can even be used for divergent cases as crosschecked (as far as possible) with the method of shanks-summation.

Things reminded me strongly of the case of Eta/Zeta-function which I reformulated with the geometric series of P (and in turn with the iteration-series in x+1) using (P + I)^-1 arriving at the Euler-numbers and Eta-function and such. However, I avoided the (P - I)^-1 -version in the beginning because of the same problem on non-invertibility; and after finding a workaround similar to Andrews idea, I could build the/a (P - I)^-1 version to eventually surprisingly arrive at the bernoulli-polynomials and the original Faulhaber/Bernoulli/"Zeta"-matrix for summing of like powers.

Now I have 2 aspects to tinker with:

I would like to understand, why and how here comes the analogy with the geometric series of Bb into the play.

The alternating geometric-series from (Bb + I)^-1 -other than the scalar version - is not twosided symmetric for infinite series of positive and of negative heights. While the scalar version sums to the central value, the matrix-version (and from this derived the alternating iteration-series) needs a certain (yet unknown) functional supplement. What about this problem for the (Bb - I)^-1 version?

Gottfried

[Gottfried]

Longer times ago I began to discuss Andrew's superlog-solution in terms of my matrix-formulae but lost the point and then the time.
Mike's question in the other thread reminded me of that sketch - here I updated it a bit. Please excuse I've done it as PDF-file - I'm a bit tired of formatting in mimetex (perhaps next week I can reformat it to such a version).
Well, it may be a bit out dated. Also it's not really complete - however, it gives a nice insight(?) into the connection with the continuum sum and with a wider field of application of a "height" (or slog-) function in iteration problems.
I've uploaded it here:
  RobbinsSlog_note2_Matrixmethod_.pdf (Size: 73.81 KB / Downloads: 1,000)

Gottfried

[bo198214]

Just want to throw in that every Carleman matrix has a natural LU-decomposition into the Carleman matrix of a translation - which is lower triangular - and the Carleman matrix of the development without its constant coefficient - which is upper triangular.

In formulas \( f(x)=f_0 + f_1 x + f_2 x^2 + \dots \),
\( \tau(x)=f_0+x \)
\( g(x)=f_1 x + f_2 x^2 + \dots \)

\( f = \tau \circ g \)
\( C[f] = \underbrace{C[\tau]}_{L} \underbrace{C[g]}_{U} \).

Though however this does not help for finding a LU-decomposition of \( C-I \) (with first row removed). The most I can get:
\( C[f] - I = LU - I = (L-U^{-1})U \)

@Gottfried:
Be aware that not (C-I) (or its transpose) is inverted but (C-I) with the first row (or column) removed!

[Gottfried]

@Gottfried:
Be aware that not (C-I) (or its transpose) is inverted but (C-I) with the first row (or column) removed!

Yes, I'm aware of this, thanks!
And -informally speaking - the inverse operation of the "removal of the 'counting'-column" is the operation of "creation of a 'counting'-column"; which gives the iteration height in terms of counting of units and even extended to fractional numbers of iterations. Not only is it interesting that such a thing is possible given a set of columns in the Carlemann/Bell-matrix (matrix-operator) and I think, that this idea extends/generalizes to other iterational problems. I'd like to see some formula more focused on this, possibly without the overhead of an inversion of an infinite square-matrix and its difficult implications...

Gottfried