Is there any particular reason we stop at the quadratic approximation typically in graphics algorithm and don't extend any further? Is the accuracy provided by the quadratic typically enough?
keenan
@jifengy Yep, there's a very good computational reason that approximations of order three and higher are relatively uncommon in computer graphics. There are fast algorithms for solving systems of linear equations $Ax = b$ (1st order), and fast algorithms for minimizing quadratic functions $x^T A x + x^T b + c$ (2nd order) which themselves often amount to solving linear systems. For instance, methods for minimizing higher-order objectives, like Newton's method, just approximate the objective quadratically at each step, then solve a linear system to get the next update direction. Beyond that, things get hard. For instance, solving systems of quadratic polynomials is, in general, as hard as any problem in $NP$. Fortunately, working with successive low-order approximations often works quite well, even for problems that are inherently nonlinear.
Is there any particular reason we stop at the quadratic approximation typically in graphics algorithm and don't extend any further? Is the accuracy provided by the quadratic typically enough?
@jifengy Yep, there's a very good computational reason that approximations of order three and higher are relatively uncommon in computer graphics. There are fast algorithms for solving systems of linear equations $Ax = b$ (1st order), and fast algorithms for minimizing quadratic functions $x^T A x + x^T b + c$ (2nd order) which themselves often amount to solving linear systems. For instance, methods for minimizing higher-order objectives, like Newton's method, just approximate the objective quadratically at each step, then solve a linear system to get the next update direction. Beyond that, things get hard. For instance, solving systems of quadratic polynomials is, in general, as hard as any problem in $NP$. Fortunately, working with successive low-order approximations often works quite well, even for problems that are inherently nonlinear.