In this paper, we present a new class of quasi-Newton methods for an effective learning in large multilayer perceptron (MLP)-networks. The algorithms introduced in this work, named LQN, utilize an iterative scheme of a generalized BFGS-type method, involving a suitable family of matrix algebras L. The main advantages of these innovative methods are based upon the fact that they have an O(nlogn) complexity per step and that they require O(n) memory allocations. Numerical experiences, performed on a set of standard benchmarks of MLP-networks, show the competitivity of the LQN methods, especially for large values of n.

Let $(1)T{\bf x} = {\bf f}$ be a linear tridiagonal system of n equations in the unknowns $x_1 , \cdots ,x_n $. It is proved that $3n - 2$ (nonscalar) multiplications/divisions are necessary to solve $(1)$ in a straight-line program excluding divisions by elements of ${\bf f}$. This bound is optimal if the cost of preconditioning of T is not counted. Analogous results are obtained in case (i) T is bidiagonal and (ii) T and ${\bf f}$ are both centrosymmetric. The existence of parallel algorithms to solve $(1)$ with preconditioning and with minimal multiplicative redundancy is also discussed.