Linear and nonlinear systems

A vast number of different applications of traditional mathematics are ultimately based on linear equations of the form u m . v where u and v are vectors (lists) and m is a matrix (list of lists), all containing ordinary continuous numbers. If v is known then such equations in essence provide explicit rules for computing u. But if only u is known, then the equations can instead be thought of as providing implicit constraints for v. However, it so happens that even in this case v can still be found fairly straightforwardly using LinearSolve[m, u]. With vectors of length n it generically takes about n^{2} steps to compute u given v, and a little less than n^{3} steps to compute v given u (the best known algorithms—which are based on matrix multiplication—currently involve about n^{2.4} steps). But as soon as the original equation is nonlinear, say u m_{1} . v + m_{2} . v^{2}, the situation changes dramatically. It still takes only about n^{2} steps to compute u given v, but it becomes vastly more difficult to compute v given u, taking perhaps 2^{2n} steps. (Generically there are 2^{n} solutions for v, and even for integer coefficients in the range -r to +r already in 95% of cases there are 4 solutions with n = 2 as soon as r ≥ 6.)