1
$\begingroup$

I have to solve system of linear algebraic equations AX=B, where A is two-dimensional matrix and all elements of main diagonal are equal to zero.

How to solve this problem? Iterational methods are not applied in this case.

One way is LU Decomposition method with reordering rows of A to get entries in main diagonal are not zero using permutation matrix. How to quickly reorder rows of matrix or find permutation matrix?

Note that matrix is very big and I have to write programm to solve SLAE in C# language, so I do not need any matlab or mathematica functions. Thanks!

  • 0
    I mean usual two-dimensional matrix nxn, with n > 500000. like this http://3.bp.blogspot.com/_264sc_gncA4/SiEOApq5oaI/AAAAAAAAAVE/DG_mb6OI7r0/s400/Session8-two-dim+array.png2012-12-27

1 Answers 1

1

Hint Use an array, p[] to hold the row permutations. The permutation vector

p =[ 3,2,1,4,5,6] 

indicates that the row corresponding to row 1 of the permuted matrix is row 3 of the original matrix, and row 3 corresponds to row 1. I.e. row 1 and 3 have been swapped.

Then use p to index into the rows of your permuted matrix matrix A. i.e. if you want to update the i'th row, you would index as

A[p[i]][...] = ... 

This effectifely swaps the two rows, with you only interchanging 2 numbers, rather than the entire two rows.

The same idea can be used for full pivotting, where the columns are permuted also.

Added later: Implementation details

Initially the p array is initialised as an unpermuted matrix, e.g.

p = [1,2,3,4,5,6]; 

If the algorithm then requires you to swap rows 1 and 3, interchange the row indices in positions 1 and 3. e.g.

p = [3,2,1,4,5,6]; 

If you then have to swap rows 2 and 3, interchange the row indices in positions 2 and 3. e.g.

p = [3,1,2,4,5,6]; 

The array p holds the indices into the rows of the matrix A. Instead of swapping the entire rows of A, by using p as a row index to A, you can swap entire rows with a single swap, rather than $n$ swaps which are required to swap the entire rows.

  • 0
    @NurlanKenzhebekov See my edit with implementation details.2012-12-27