Linear algebra computable

Question

I'm working in a linear algebra software, but I have a problem.

If I try to reduce the matrix to reduced echelon form, many resources will be consumed. That is, if I perform many basic operations such as change rows positions, multiply, sum, etc, then this would be very expensive to implement.

So I'm looking for a more effective procedure such as a formula or something more elegant.

Is there any way?

Answer 1

There is no formula to get the row echelon form of a matrix. You can implement the intermediate steps as matrix multiplications with elementary matrices.

You should look into linear algebra libraries for whatever language you are working in. There are almost certainly efficient implementations for any common operation.

Answer 2

It's the nature of the beast. Reducing to row echelon form requires $O(n^3)$ operations for a general $n\times n$ matrix. Unless you are working in a purely functional language, it is important to operate on a single matrix in-place, and not make a lot of copies of rows as you proceed. If you are dealing with matrix entries of a fixed size, such as floats or finite field elements, then there are blocked algorithms that help with memory locality. For integer matrices, you could look into the Bareis algorithm.

Having said all that, your best bet is to look for a well-written library (such as BLAS or LAPACK) that already implements these fundamental linear algebra algorithms.