여기서 (c)를 해결하려하는데 Matlab으로 아무리 코드를 짜봐도 호너의 법칙을 적용하는게 압도적으로 flops가 적음...
the obvious method는 당연히 p(A)b = c_0*b + c_1*A*b + c_2*A*A*b ... 를 의미할텐데
c = [1,2,3,4,5,6,7];
m = 30;
x = ones(m);
b = ones(m, 1);
result = c(1) * eye(m);
power = eye(m);
n = length(c);
flops = 0;
for i = 2:n
temppower = zeros(m, m);
for j = 1:m
for k = 1:m
for l = 1:m
temppower(j, k) = temppower(j, k) + power(j, l) * x(l, k);
flops = flops + 2;
end
% since we're adding the value to 0, we're wasting one addition
% theoretically this isn't necessary so we decrease it
flops = flops - 1;
end
end
power = temppower;
for j = 1:m
for k = 1:m
result(j, k) = result(j, k) + c(i) * power(j, k);
flops = flops + 2;
end
end
end
tempresult = zeros(m, m);
for j = 1:m
for k = 1:m
tempresult(j, k) = tempresult(j, k) + result(j, k) * b(k, 1);
flops = flops + 2;
end
% Same as line #18
flops = flops - 1;
end
result = tempresult;
이게 (a)를 해결하기 위해 짠 코드고 계산했던 (n-1)(2m^3+m^2)+2m^2-m flops랑 일치하는거 보면 코드엔 문제가 없어보임
c = [1,2,3,4,5,6,7];
m = 30;
x = ones(m);
b = ones(m, 1);
n = length(c);
result = c(1) * diag(b);
flops = m;
for i = 2:n
power = eye(m);
for p = 1:i-1
temppower = zeros(m, m);
for j = 1:m
for k = 1:m
for l = 1:m
temppower(j, k) = temppower(j, k) + power(j, l) * x(l, k);
flops = flops + 2;
end
% since we're adding the value to 0, we're wasting one addition
% theoretically this isn't necessary so we decrease it
flops = flops - 1;
end
end
power = temppower;
end
for j = 1:m
for k = 1:m
result(j, k) = result(j, k) + c(i) * power(j, k) * b(k, 1);
flops = flops + 3;
end
end
end
위와 비슷한 방식으로 (c) 를 해결하기 위한 코드를 짰는데 m=30에서 거의 3~4배 flops 차이를 보임
행렬의 곱셈을 여러번 한다는 점에서 애초에 호너의 법칙을 적용하는게 유리해보이는데
왜 문제에서는 호너의 법칙이 연산량에 큰 이득을 주지않는다는거임?
