This paper is concerned with piecewise-affine (PWA) functions as Lyapunov function candidates for stability analysis of time-invariant discrete-time linear systems with saturating closed-loop control inputs. Using a PWA model of saturating closed-loop system, new necessary and sufficient conditions for a PWA function be a Lyapunov function are presented. Based on linear programming formulation of these conditions, an effective algorithm is proposed for construction of such Lyapunov functions for estimation of the region of local asymptotic stability. Compared to piecewise-linear functions, like Minkowski functions, PWA functions are more adequate to capture the dynamical effects of saturation nonlinearities, giving strictly less conservative results. The complexity of the proposed approach is polynomial in state dimension and exponential in saturating control dimension, being hence appropriate for problems with large state dimension but with few saturating inputs. (C) 2002 Elsevier Science Ltd. All rights reserved.381221772184