Patent Document ID: 9058302
Application ID: 13430028
Patent Flag: 1

Claim One:
1. A method for a combined matrix-vector and matrix transpose-vector calculation for a block-sparse matrix A that computes q=Ap and qt=A T (pt) to iteratively solve a system of equations A*Δv=b for updating a simulation of physical objects in an interactive computer environment, wherein the vector Δv represents a change in velocity of the physical objects and the vector b represents an expected position of the physical objects, and wherein the vectors p, pt, q, and qt are variables for performing a biconjugate gradient algorithm, the interactive computer environment having a processor, a memory and a display, the method comprising: generating a set of representations of objects in the interactive computer environment; partitioning the set of representations into a plurality of subsets such that objects in any given set interact only with other objects in that set; storing the matrix A as a collection of nonzero subblocks chained in a first dimension, with one chain for each position in a second dimension, such that each subblock comprises an index giving its position in the first dimension and the subblock elements are stored in groups corresponding to a register size and ordered reading along the first dimension within the group; applying a biconjugate gradient algorithm to solve A*Δv=b for the vector Δv of velocity changes applied to each object, wherein a single matrix-vector multiplication routine is called once per iteration to read the matrix A a single time and produce two matrix-vector products from the single time, one matrix-vector product involving A and the other involving the transpose of A, to determine the value of two vectors used to update the residuals used in the biconjugate gradient algorithm, without explicitly forming the transpose of A, wherein applying the biconjugate gradient algorithm comprises computing q=Ap and qt=A T (pt) by: for each subblock chain along the second dimension, performing: for each position along the first dimension of the subblock, initializing a register as an accumulator; for each position along the second dimension of the subblock, filling a register with copies of the element of the p vector corresponding to that position; for each subblock in the chain, performing: updating the elements of q corresponding to the subblock elements along the second dimension, based on appropriate matrix elements and copies of the p vector elements corresponding to the horizontal positions in the subblocks; and updating the accumulators based on the products of the matrix elements with the elements of pt corresponding to the positions along the first dimension; and for each accumulator, updating the element of qt corresponding to the chain offset by the accumulator's position within the subblock, based on a sum of individual elements of the accumulator; and applying, by a computer processor, the vector Δv of velocity changes to determine a next state of the simulated objects.