Forum Discussion
Would you recommend the use of Excel complex numbers where performance is required?
I think this is the file I sent to you attached to a LinkedIn message but I will put it here before I lose it! Having written the FFT, I made the slight modifications to produce the IFFT and then went on to implement the two functions as a convolution by complex multiplication of the the two FFTs and applying the IFFT to the product.
The uses I had in mind were for calculating the depreciation of capital expenditure or the cash balances that result from the delay between invoice and payment. What reminded me of all this was a blog post by Jon Peltier.
Improved Excel Lambda Moving Average - Peltier Tech
The Convolveλ function represents overkill, taking 2.5ms rather than 0.5ms for Jon's direct approach but I rather like the way the convolution can be written so that the average does not lag the data points. I might be a bit more competitive were we averaging 4096 points over a spread of 256.
= Convolveλ(datarange, nPoints, 32)The convolution seems to be pretty flexible in terms of having both a number of different applications and allowing experimentation to look at the effect of selecting different kernels for the smoothing. In my latest attempt I chose to use the binomial coefficients which I then looked up and found it is known as a Gaussian Filter, published in 1958.
Both the smoothness and the fit look pretty good to me, though Jon's dataset is so noisy that it is difficult to judge.
I was surprised by the work you published on GitHub. Whilst I had anticipated that there would be others working with FFT who would be far more knowledgeable than I (I had never even thought to look under the covers of the discrete form of Fourier transformations), I did not anticipate that any would be working with Excel! I wrongly assumed it would be all Python or MATLAB/Simulink.
- No, I didn't consider a BigInt implementation, nor a NTT transform. My use case is probability: distribution of sums of random variables
I confirmed your formula works.
I think my full objective would to be to write an LDLᵀ decomposition routine for very sparce matrices. It would need to be accompanied by forward and backward substitutions to allow for the solution of linear equations. The matrices are typically stored using a skyline matrix scheme and the fill-in from the LDLᵀ / Choleski algorithm fits within the same skyline.
anupambit1797 maybe
CHOLESKY(X) =LET( i, SEQUENCE(ROWS(X)), init, INDEX(X, , 1) / INDEX(X, 1, 1) ^ 0.5, fn, LAMBDA(A, i, LET(x, INDEX(X, , i) - MMULT(A, TOCOL(CHOOSEROWS(A, i))), x / INDEX(x, i) ^ 0.5) ), REDUCE(init, DROP(i, 1), LAMBDA(A, i, HSTACK(A, fn(A, i)))) )This returns a lower triangular matrix L (when formatted as a decimal), one can then check MMULT(L,TRANSPOSE(L)) returns the original matrix, e.g. X ={6,3,4,8;3,6,5,1;4,5,10,7;8,1,7,25}.
Further adjustments may be needed for near-singular matrices. As Peter points out the REDUCE/HSTACK hack is required at present due to a lack of a generalised SCAN function.
aaltomani I started looking at building a 'BigInt' function library using FFT methods and wanted to extend with the Number Theoretic Transform (see references here) - I wondered is that something that had been considered as an addition to your gist above?
I find it something of a surprise that it is possible to deploy quite advanced numerical algorithms as a spreadsheet formula. I suspect there is a long way to go before we see Excel solutions deployed to the full.
One thing that still troubles me is the limitation preventing the return of 'arrays of array' from helper functions. Most algorithms I implement require arrays of arrays and REDUCE/VSTACK is a cumbersome way of achieving what should be inbuilt functionality.
To have multidimensional arrays displayed as a two 2D array rather than mapped to 1D memory locations helps algorithm development because one dimension can be used to hold the input to each specific calculation whilst the other is free to to hold multiple instances of the calculation. That reduces the need for the complicated manipulation of indices.
HiPeterBartholomew1 , it's a suggestion from myside.. haven't implemented anything yet.. I rely on you(your Expertise) guys for this 🙂
Br,
Anupam
Have you implemented a Lambda function for this or is it simply a suggestion for a worthwhile task? It is an algorithm I have thought of implementing, if only because it is one I used in the early days of finite element analysis in which the matrix represented the strain energy of possible deformations and was necessarily positive definite.
- It was pretty fun to write and optimize it! Matlab/Python and friends are very difficult to deploy for other users. Lambda function live in standard spreadsheets, they don't even need a Macro-Enabled file!
