Patent Document ID: 8175853
Application ID: 12057693
Patent Status: 1

Claim One:
1. A method for a combined matrix-vector and matrix transpose-vector calculation for a block-sparse matrix A which computes q=Ap and qt=A T (pt), for iteratively solving a system of equations A*Δv=b, wherein A T represents transpose of matrix A, Δv represents change in velocity to be applied to each object, b represents an expected position of objects, for updating a simulation of physical objects in an interactive computer environment, said interactive computer environment having a processor, a memory in which said matrix A and vectors p, pt, q, and qt are stored, and a plurality of registers capable of representing and operating on multiple matrix or vector elements in a single operation, the method comprising: storing, by the processor, 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 includes an index giving its position in said first dimension and subblock elements are stored in groups corresponding to a register size and ordered reading along said first dimension within the group; initializing, by the processor, each element of the vector q to zero; for each subblock chain along said second dimension, performing: for each position along said first dimension of the subblock, initializing, by the processor, a register to all zeroes as an accumulator; for each position along said second dimension of the subblock, filling, by the processor, a register with copies of elements of the p vector corresponding to that position; for each subblock in said chain, performing: reading, by the processor, all groups of elements of said subblock into the registers; reading, by the processor, the elements of the vector q corresponding to the subblock elements along said second dimension into the one or more registers, adding to said registers sum of products of appropriate registers of matrix elements and the copies of the p vector elements corresponding to horizontal positions in the subblocks, and use resulting register values to update said elements of the vector q corresponding to said subblock elements along said second dimension; forming, by the processor, products of the matrix elements with elements of the vector pt corresponding to the positions along first axis and adding the products to the corresponding accumulators; for each accumulator, summing, by the processor, individual elements of the accumulator and storing result as element of the vector qt corresponding to the chain offset by the accumulator's position within the subblock.