1
$\begingroup$

Given: A Square Matrix where each entry is an integer (either positive or negative). The magnitude of each integer entry is at most $m$ bits. The size of the Square matrix is $n \times n$.

Objective: Reduce the Square Matrix to a Diagonal Matrix form using Gaussian Row Elimination.

Query: What is the most efficient algorithm and its time complexity for the above?

Comment: Most sources discuss the number of operations but not the total computational complexity. The obvious method is to use the text book method of row elimination. But I am assuming in the worst case, it is possible for the intermediate matrix entries to blow up exponentially in their size (w.r.t. $m$). Thus, I am not clear.

Can someone help with the most efficient algorithm to achieve the above and its time complexity? (a clear reference to a textbook/source where that algorithm as well as its complexity is derived would be equally great).

P.S. I was suggested this link Link but it is not very clear (either Algorithm or its complexity)

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I'm not sure if you achieve any better time complexity for the entries being integers like you state. You can find a description of this in the following books. Note that Gaussian Elimination doesn't do what you say.

  • Numerical Linear Algebra -Trefethan and Bau
  • Applied Numerical Linear Algebra - Demmel
  • Matrix Computations - Golub

There are more efficient methods that are built upon using block matrices and randomized matrices however the following method is Gaussian Elimination or the LU Decomposition. Given $$ A \in \mathbb{C}^{m \times m} $$ The elimination process is equivalent to the following $$L_{m-1}\cdots L_{2}L_{1}A = U $$ Here we set $$ L = L_{1}^{-1}L_{2}^{-1}\cdots L_{m-1}^{-1} \implies A= LU $$ This yields the following algorithm. enter image description here with an operation count of $$ \approx \frac{2}{3}m^{3} \textrm{flops} $$

If you are attempting to say diagonalization for eigenvalues. It is possible to use the Cholesky decomposition to perform the eigendecomposition. In which case the flop count would be if you had structure. But you're just going about this all wrong.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.