Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Out of core ways to use backslash operator for large dense systems

Subject: Out of core ways to use backslash operator for large dense systems

From: Vineet

Date: 15 Sep, 2009 14:06:02

Message: 1 of 5

Hi
Is there a way to use backslash operator (\) for linear systems of equation when you cannot store the matrix in memory. Like for example if A is dense 8500*85000 matrix which cannot be stored in the memory and A\b is to computed, where b is column vector of appropriate dimensions then which would be the most efficient out of core algorithm (external memory where parts of the matrix are stored on a hard drive) to do it on a single desktop in a reasonable amount of time. I know of parallel solutions based on LU decomposition of matrix or Cholesky decomposition for positive definite matrix which are based on block decomposition of matrices which however requires block cyclical distribution of matrix (depending on the number of nodes available) and thereafter Scalapack can be used to obtain the solution.
• The problem for which is to be done requires running of optimization routines for optimizing Restricted Maximum Likelihood function for 42 parameters and generate CO2 flux estimates for north America through inverse modeling
Any ideas and suggestion would be greatly helpful

Vineet

Subject: Out of core ways to use backslash operator for large dense systems

From: Matt

Date: 15 Sep, 2009 14:37:02

Message: 2 of 5

"Vineet " <vineet-yadav@gmail.com> wrote in message <h8o70a$crg$1@fred.mathworks.com>...
> Hi
> Is there a way to use backslash operator (\) for linear systems of equation when you cannot store the matrix in memory. Like for example if A is dense 8500*85000 matrix which cannot be stored in the memory and A\b is to computed, where b is column vector of appropriate dimensions then which would be the most efficient out of core algorithm (external memory where parts of the matrix are stored on a hard drive) to do it on a single desktop in a reasonable amount of time. I know of parallel solutions based on LU decomposition of matrix or Cholesky decomposition for positive definite matrix which are based on block decomposition of matrices which however requires block cyclical distribution of matrix (depending on the number of nodes available) and thereafter Scalapack can be used to obtain the solution.
> • The problem for which is to be done requires running of optimization routines for optimizing Restricted Maximum Likelihood function for 42 parameters and generate CO2 flux estimates for north America through inverse modeling
> Any ideas and suggestion would be greatly helpful
============

You could look at "doc memmapfile"

memmapfile essentially allows a MATLAB array to store its data in a file, but otherwise to interface with that variable in the usual way. Of course, if it works, it will be slow as hell.

It might be of more help to you to see how this matrix arises. Knowing the structure could reveal cheaper structured solutions.

Subject: Out of core ways to use backslash operator for large dense systems

From: Matt

Date: 15 Sep, 2009 15:20:19

Message: 3 of 5

"Vineet " <vineet-yadav@gmail.com> wrote in message <h8o70a$crg$1@fred.mathworks.com>...
> Hi
> Is there a way to use backslash operator (\) for linear systems of equation when you cannot store the matrix in memory. Like for example if A is dense 8500*85000 matrix which cannot be stored in the memory and A\b is to computed, where b is column vector of appropriate dimensions then which would be the most efficient out of core algorithm (external memory where parts of the matrix are stored on a hard drive)
====

One other point is that, for dense systems of the size you're taliking about, people don't usually use closed form solvers like A\b. Rather, they would normally use an iterative method like conjugate gradient to minimize

norm(A*x-b).^2

In this, case, you only need to access A in order to compute the gradient

Gradient= A'*(A*x-b)

For this, you could compute quantities A*x and A.'*y by accessing A in chunks from the hard-drive...

Subject: Out of core ways to use backslash operator for large dense systems

From: Bruno Luong

Date: 15 Sep, 2009 16:14:03

Message: 4 of 5

"Vineet " <vineet-yadav@gmail.com> wrote in message <h8o70a$crg$1@fred.mathworks.com>...
> Hi
> Is there a way to use backslash operator (\) for linear systems of equation when you cannot store the matrix in memory. Like for example if A is dense 8500*85000 matrix

Just to be sure : You have 10 times more unknowns than equations?

Bruno

Subject: Out of core ways to use backslash operator for large dense systems

From: Edric M Ellis

Date: 16 Sep, 2009 07:34:06

Message: 5 of 5

"Vineet " <vineet-yadav@gmail.com> writes:

> Is there a way to use backslash operator (\) for linear systems of equation
> when you cannot store the matrix in memory. Like for example if A is dense
> 8500*85000 matrix which cannot be stored in the memory and A\b is to computed,
> where b is column vector of appropriate dimensions then which would be the
> most efficient out of core algorithm (external memory where parts of the
> matrix are stored on a hard drive) to do it on a single desktop in a
> reasonable amount of time. I know of parallel solutions based on LU
> decomposition of matrix or Cholesky decomposition for positive definite matrix
> which are based on block decomposition of matrices which however requires
> block cyclical distribution of matrix (depending on the number of nodes
> available) and thereafter Scalapack can be used to obtain the solution.

The Parallel Computing Toolbox incorporates SCALAPACK functionality for
performing backslash on large dense distributed matrices. More info about
Parallel Computing Toolbox:

http://www.mathworks.com/products/parallel-computing

Here's a list of functions that you can use to operate on distributed matrices:

http://www.mathworks.com/access/helpdesk/help/toolbox/distcomp/bqxooam-1.html

As it happens, backslash is one of the HPC Challenge problems, here's our entry
from 2008, which shows performance of the large dense backslash operator:

<http://www.hpcchallenge.org/presentations/sc2008/matlab-SC08%20HPCC%20Presentation.pdf>

Cheers,

Edric.

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us