$\mathbf{A}$ is an $(n+1) \times (n+1)$ matrix. It can be obtained as follows:
$\textbf{A} = \left[ \matrix{1 & 1 & 1 & \cdots & 1 \cr
x_0 & x_1 & x_2 & \cdots & x_{n} \cr
\vdots & \vdots & \vdots & \cdots & \vdots \cr
x_0^n & x_1^n & x_2^n & \cdots & x_n^{n}}\right] \left[ \matrix{1 & x_0 & x_0^2 & \cdots & x_0^n \cr
1 & x_1 & x_1^2 & \cdots & x_1^{n} \cr
\vdots & \vdots & \vdots & \cdots & \vdots \cr
1 & x_n & x_n^2 & \cdots & x_i^{n}}\right] $
Note that the decomposition doesn't involve any summation and can be easily computed using simple indexing and power operations. The matrix multiplication is an effective operator to compute the final matrix $\mathbf{A}$. This is both efficient and easy to implement.
The matrix on the right is simply a Vandermonde matrix with an added column (right-most). Here is a MATLAB 2-liner to implement this:
% x is the input column vector, n is the number of elements e.g. n=length(x)
W = [ fliplr(vander(x)) (x.^n)];
A = W'*W;
This should work faster than for-looping in MATLAB since vander
function doesn't contain any loops. It is also definitely shorter and cleaner.
I believe that making a quick remark is important here. Unlike common belief, when properly implemented matrix multiplication is not $O(N^3)$, but $<O(N^{2.4})$. Many available packages are already very optimized. Using vector instruction sets, along with parallelization brings further speed-up. However, the theoretical complexity never comes to $O(N^2)$ which is achieved via for-looping. This approach is only neater and faster in MATLAB for small sized matrices (up to ~ N<1500).
Also note that, even if the matrix notation is used here, the multiplication could still benefit from the special structure of these matrices. If one is to utilize this property, similar complexity can be obtained.
for
loops? Use a loop to compute the first row then use another loop to compute the rest of the rows by copying values from the row above and then compute the last value in the row. $\endgroup$n
degree, because I can not imagine any universal algorythm for that - only for particular degree, not any. I have calculated polynomial coefficients using the Vandermonde matrix and appended it withy
data values and then I have used Gauss elimination. But I would also like to know how can I do it using another method or to know, whether it is not efficient. $\endgroup$n
"? Just use n to define your loop limits. Here's a fully functional solution for MATLAB (just definen
andx
first):A = zeros(n+1); for j=0:n, A(1,j+1)=sum(x.^j); end, for i=1:n, A(i+1,1:n)=A(i,2:n+1); A(i+1,n+1)=sum(x.^(n+i)); end
$\endgroup$