Browse Prior Art Database

Marginalizing Dense Multi-Dimensional Matrices

IP.com Disclosure Number: IPCOM000022264D
Publication Date: 2004-Mar-03
Document File: 2 page(s) / 37K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method that performs fast and cache-friendly marginalization, and a generalized multiplication of dense multi-dimensional matrices. Benefits include an algorithm that outperforms current analogs.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 59% of the total text.

Marginalizing Dense Multi-Dimensional Matrices

Disclosed is a method that performs fast and cache-friendly marginalization, and a generalized multiplication of dense multi-dimensional matrices. Benefits include an algorithm that outperforms current analogs.

Background

In statistical computing, there is a need for operations on multi-dimensional matrices. Among these are marginalization of the matrix, and a generalized element-wise multiplication of the matrices.

For example, matrix A is a function of 10 binary variables x_1…x_10, and might require a sum A over x_2, x_5 and x_9 in order to obtain a new matrix defined on x_1, x_3, x_4, x_6, x_7, x_8, x_10. This is a very common type of operation for probabilistic multivariate analysis.

General Description

The following is the current way of solving the problem:

For each element e in the destination matrix B, find all elements in source matrix A corresponding to e and sum them up on the loop end.

However, this approach creates a significant number of cache misses, since the memory access pattern to the source matrix is chaotic most of the time. The disclosed method uses a more cache-friendly approach; a brief description of the algorithm is as follows:

1.      Initialize the destination matrix with zeros.

2.      For each element e from the source matrix, find all corresponding elements from the destination matrix and update them by adding the value of the e loop end

Most of the time, for each element from the destination matrix there...