Limited memory solution of bound constrained convex quadratic problems arising in video games

¹ Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford, OX1 3QD, UK.
² Computer Sciences Department, University of Wisconsin, 1210 West Dayton Street, Madison, Wisconsin 53706, USA.
³ Laboratoire XLIM, Université de Limoges, Faculté des Sciences et Techniques, 123, avenue Albert Thomas, 87060 Limoges, France; armand@unilim.fr

Received: 30 March 2005
Accepted: 23 June 2006

Abstract

We describe the solution of a bound constrained convex quadratic problem with limited memory resources. The problem arises from physical simulations occurring within video games. The motivating problem is outlined, along with a simple interior point approach for its solution. Various linear algebra issues arising in the implementation are explored, including preconditioning, ordering and a number of ways of solving an equivalent augmented system. Alternative approaches are briefly surveyed, and some recommendations for solving these types of problems are given.