I'm working with the PCx code and can't figure out how the Mehrotra format for matrix work. The code describing the data structure are

typedef struct {
    int NumRows, NumCols, Nonzeros;
    int *pBeginRow;
    int *pEndRow;
    int *Row;
    double *Value;
} sparseMatrix;

asked 12 Feb '13, 07:00

raniere's gravatar image

raniere
31
accept rate: 0%


I have not seen the code, so this is an educated guess.

That data structure looks like a compressed row format with an extra array (pEndRow) for convenience and to minimize re-allocations due to fill-in.

See here for a simple explanation of the basic compressed row/column format.

It may be that the end pointer points to the last nonzero in that row at any given point, but that some space is left between that number and the next row start. This approach leaves some empty space in the data structure to account for fill-in (i.e., when factorization add non-zeros to the matrix).

link

answered 12 Feb '13, 09:40

Leo's gravatar image

Leo
60613
accept rate: 12%

The two most common schemes for storing sparse matrices are "Compressed Row Storage (CRS)" and "Compressed Column Storage (CCS)." This struct looks like it would be right for compressed row storage, except for the "int *Row", which would normally be "int *Col"

Whatever scheme you use there has to be some to way to implicitly or explicitly identify the row and column of each entry, and there's no place here to do that. One possibility is that the author was just sloppy in writing "int *Row" instead of "int *Col" It's also possible that this structure is only being used for symmetric matrices, and the author is using the fact that A(i,j)=A(j,i).

My advice would be to read up on CRS/CCS to understand how this scheme is commonly used and then examine the code that refers to this structure and verify what's going on. Or, you could contact the author of the code.

link

answered 12 Feb '13, 09:31

Brian%20Borchers's gravatar image

Brian Borchers
1.1k15
accept rate: 17%

edited 12 Feb '13, 09:32

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×96
×30
×3
×3
×1

Asked: 12 Feb '13, 07:00

Seen: 574 times

Last updated: 12 Feb '13, 09:40

OR-Exchange! Your site for questions, answers, and announcements about operations research.