op_fitz - Evaluate the Fitzpatrick function of a given operator on a grid using the LLT2d algorithm.
Evaluates the Fitzpatrick function with order n of an operator A on a grid (x,x*).
This function uses a recursive algorithm that employs LLT2d to achieve a running time of O(n*m^2 + m*Nxstar + N). When m==Nx==Nxstar, the running time is O(m^3).
F(A, 1, x, xstar) = x * xstar' F(A, 2, x, xstar) = max [ x*astar + a*xstar - a*astar - I(a,astar*) ] (a,astar) in A F(A, 3, x, xstar) = max [ x*astar2 + a1*xstar + f(a1,astar2) ] (a1,astar2) in A f(a1, a2) = max [ -a1*astar1 - a2*astar2 - I(a1,astar1) - I(a2,astar2) ] (astar1,a2) in A where I is the indicator function for the set A (I(x)=0 if x is in A, +%inf otherwise). m = size(A, 2); Nx = size(x, 1); Nxstar = size(xstar, 1); N = Nx * Nxstar;
a = -2:2; astar = 3*a - a + 3; x = -3:3; xstar = -3:3; F1 = op_fitz([a; astar], 1, x, xstar); F2 = op_fitz([a; astar], 2, x, xstar); F3 = op_fitz([a; astar], 3, x, xstar); clf(); alpha=60; theta=-60; subplot(131); plot3d(x, xstar, F1, alpha=alpha, theta=theta); subplot(132); plot3d(x, xstar, F2, alpha=alpha, theta=theta); subplot(133); plot3d(x, xstar, F3, alpha=alpha, theta=theta);
op_fitz_brute, op_fitz_direct, op_fitzinf, plq_fitzinf0, plq_fitzinf0_direct, plq_rock,
Bryan Gardiner, University of British Columbia, BC, Canada