0
votes
0answers
40 views

Fastest Algorithms for Determining the Nullity of a Matrix

How exactly does one go about determining the Nullity of a Matrix quicker than simply running Gaussian Elimination on the matrix itself? To be perfectly honest I can't think of a method that doesn't ...
1
vote
0answers
26 views

Solving tridiagonal matrices where the top left element is zero

If I have a matrix like this: $$ \left[\begin{array}{rrrrrrrrr|r} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & ...
7
votes
1answer
132 views

Fast algorithm for approximating Eigenvalue distribution of large sparse matrix

I am interested in the eigenvalue distribution of a huge $2^{16}$x$2^{16}$ Hermitian sparse matrix with spectrum contained in $[-1,1]$. That is I don't need to know all eigenvalues exactly, but rather ...
0
votes
0answers
22 views

Iteratively solve linear equations with rank-1 updates on LHS and RHS

What is the best way to iteratively solve updating equations of the form $$ Ax=b $$ $$ (A+c_1v_1^\intercal)x_1=b+ \alpha_1 d_1 $$ $$ (A+c_1v_1^\intercal+c_2v_2^\intercal)x_2=b+\alpha_1d_1+\alpha_2d_2 ...
0
votes
0answers
38 views

algorithm to separate the roots of a polynom

I need an algorithm to separate the roots of a polynom. The degree of the polynom is n (10 < n < 20) and the polynom has the same number of roots as it's degree. All roots are real. I need to ...
2
votes
2answers
50 views

Solve linear equation system $A'Ax=A'Bz$

For $A$ and $B$ known matrices which are not square matrices, I have the following equation sistem i would like to solve numerically \begin{equation} A'Ax=A'Bz \end{equation} I want to know which is a ...
0
votes
0answers
35 views

Tridiagonal Gaussian Elimination: Band Storage

I was given this algorithm for Tridiagonal Gaussian Elimination: Band Storage for i = 2:N if W(3,i-1) is zero error('the matrix is singular or pivoting is required') end m = W(4,i)/W(3,i-1) ...
0
votes
1answer
72 views

Backward stable algorithm

Assume we have fixed unitary matrices $Q_1, \dots, Q_k \in \mathbb{C}^{m,m}$ and a matrix $A \in \mathbb{C}^{m,n}$ which can be perturbed. How can we proof that the algorithm on computing the product ...
0
votes
1answer
55 views

Need Help! Recognizing types of errors: Truncation and Roundoff

I am a little unclear on the difference between the two. What exactly are they? As simplified as possible :) How can i recognize them and identify parts of formulas or algorithms that would give ...
1
vote
1answer
65 views

Convergence of Recursive algorithms

In a kind of signal processing problem I faced the following recursive (boot-strap) algorithm: $$R_{k} = R_{k-1} + (y_k-H s_{k-1})*(y_k-H s_{k-1})^T$$ $$s_k = (H^T R_k^{-1} H)^{-1} H^T R_k^{-1} ...
1
vote
1answer
163 views

How do deal with a giant sparse matrices?

Someone point me in the right direction. I'm looking to do some heavy-duty manipulation of some really large and often very sparse matrices. Naturally, this problem overlaps programming heavily (I ...
1
vote
1answer
64 views

A minimization problem

Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \left\|\frac{w}{x}\right\|,~w,u\in \Bbb{R}^n$$ where $$\frac{w}{x}=\left(\frac{w_1}{x_1},\ldots, \frac{w_n}{x_n}\right)$$ $$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$ ...
3
votes
2answers
183 views

Is the QR algorithm for computing eigenvalues efficient for today's standards?

I was looking at the QR factorization algorithm of a matrix to approach eigenvalues. At the Wikipedia page they state that it was developed in the 50's and took over the LR algorithm. They also state ...
1
vote
0answers
48 views

Algorithms for Performing Large Integer Matrix Operations w/ Numerical Stability

I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ...
8
votes
1answer
1k views

What would be a good method for finding the submatrix with the largest sum?

This question is from an ongoing contest which ends in 4 days. It is this problem from the October Challenge. Given:A Matrix (Not necessarily square) filled with negative and positive ...
2
votes
2answers
452 views

Fast algorithm for LU factorization

If A is a symmetric matrix, is there a fast algorithm for LU factorization? I know this algorithm for non-symmetric matrix. ...
0
votes
1answer
477 views

calculating matrix rank with gaussian elimination

[The answer to my problem has been found: it was a simple sign error. the pseudo code below is fine] I have implemented an algorithm in c++ that should calculate the matrix rank of a given n x m ...
2
votes
1answer
252 views

Confusion with “trivial Givens rotations” being used to eliminate values in a vector

I am currently studying the QR algorithm described in Computing the eigenvalues of a companion matrix and have come to something that has me scratching my head. I'm trying to work this method out on ...
1
vote
0answers
142 views

The fastest algorithm of computing Principal eigenvector of a non-negative-entries matrix

I am studying the QR algorithm, is it the fastest one in this situation?
2
votes
1answer
96 views

Fast Algorithm For Adding An Equation To A System?

Assume an $N \times N$ matrix $A$ and a length $N$ vector $b$. I've already solved the system $Ax = b$ for $x$ using standard methods. (If you want you can assume that I have the inverse of $A$ as ...
2
votes
0answers
704 views

QR with column pivoting

Golub and van Loan's algorithm 5.4.1 for QR factorization is suitable as a rank revealing algorithm. The results are R, Q with the subdiagonal elements stored in "factored form" and the column ...
3
votes
1answer
182 views

Finding SVD efficiently for $AB^T$

I posted this on cs theory yesterday but did not get an answer and hence I am posting here. I have a low rank matrix given as $AB^T$ where $A,B \in \mathbb{R}^{n \times p}$ and $p \ll n$. (I know $A$ ...