SC13 Home > SC13 Schedule > SC13 Presentation - A Computationally Efficient Algorithm for the 2D Covariance Method

SCHEDULE: NOV 16-22, 2013

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

A Computationally Efficient Algorithm for the 2D Covariance Method

SESSION: Matrix Computations


TIME: 11:00AM - 11:30AM

SESSION CHAIR: Laura Grigori

AUTHOR(S):Oded Green, Yitzhak Birk


The estimated covariance matrix is a building block for many algorithms, including signal and image processing. The Covariance Method is an estimator for the covariance matrix, favored both as an estimator and in view of the convenient properties of the matrix that it produces. However, the considerable computational requirements limit its use. We present a novel computation algorithm for the covariance method, which dramatically reduces the computational complexity (both ALU operations and memory access) relative to previous algorithms. It has a small memory footprint, is highly parallelizable and requires no synchronization among compute threads. On a 40-core X86 system, we achieve 1200X speedup relative to a straightforward single-core implementation; even on a single core, 35X speedup is achieved.

Chair/Author Details:

Laura Grigori (Chair) - INRIA

Oded Green - Georgia Institute of Technology

Yitzhak Birk - Technion - Israel Institute of Technology

Add to iCal  Click here to download .ics calendar file

Add to Outlook  Click here to download .vcs calendar file

Add to Google Calendarss  Click here to add event to your Google Calendar

The full paper can be found in the ACM Digital Library