0
votes
0answers
32 views

What is the space complexity of inverting a real valued sparse banded diagonal symmetric matrix?

Of course, when I say ``inverse'' what I really mean is solving a system of equations $Ax=b$ where $A$ is sparse, banded diagonal, symmetric, real valued $N \times N$ with a bandwidth of $k$. I know ...
2
votes
1answer
65 views

A Matrix Optimization Problem

Given an $n\times d$ matrix $Y$, I am looking for an algorithm to find an $n$-vector $\mathbf{v}$ ($0\le \mathbf{v}_i\le 1$ for all $i$) that minimizes $\sum_{i:X_i<0}X_i$, where $X:= \mathbf{v} ...
1
vote
0answers
131 views

How to compute this recursion in linear time?

Can the following iterative update on a $n$-element vector $\mathbf{x}_t$ be computed in $O(n)$ computations? \begin{align*} \mathbf{x}_{t+1} & = a_t\mathbf{y}_t + \mathbf{A}_t \mathbf{x}_t \,,\\ ...
0
votes
0answers
265 views

Exact inversion of matrix complexity (by Gaussian elimination)

I would like to check if what I have done is correct. Please, any input is appreciated. Problem statement: Consider a non-singular matrix $A_{nxn}$. Construct an algorithm using Gaussian elimination ...
2
votes
0answers
60 views

Asymptotic behavior of $L^2$ norm for increased matrix dimensions

I am playing with matrices which are linear combinations of identity matrix, Pauli spin matrices, $\sigma_x$ and $\sigma_z$ or their tensor products. For example, let the matrix be $H$. So, $H$ could ...
1
vote
0answers
290 views

Solving large, sparse system of linear equations

I have a system of linear equations as follows: $$(A+I)x=B$$ where $I$ is the $n\times n$ identity matrix, $A$ is a $n\times n$ matrix such that the first and last rows are blank, and, for every ...
7
votes
1answer
115 views

complexity of matrix multiplication

For $n\times n$ dimensional matrices, it is known that calculating $\operatorname{tr}\{AB\}$ needs $n^2$ scalar multiplications. How many scalar multiplications are needed to calculate ...
2
votes
0answers
186 views

Pseudo inverse of matrix: SVD vs $A^{T}(A.A^{T})^{-1}$

For a C++ implementation I have to calculate Moore Penrose Inverse (AKA pseudo inverse) of non squared matrices. I was wondering ...
2
votes
1answer
174 views

calculating the determinant of an $n \times n$ integer matrix

I want to write a polynomial algorithm for calculating the determinant of an $n \times n$ integer matrix. There are various codes in different programming languages on the web but unfortunately I am ...
0
votes
0answers
667 views

How to calculate an orthonormal basis for a matrix?

Are there any specific, easy to compute, algorithms to build an orthonormal basis for a matrix in which each column has length one?
1
vote
1answer
208 views

How to deduce the psition mapping of entries of a matrix?

I would be thankful if any peer shed light on me. Assume that the mapping of a set is unknown. By knowing n number of E element sets and the transformed sets with positioned elements, How can I ...
4
votes
2answers
87 views

How to recover a shuffled matrix

Suppose that I have a matrix $A$. $A$ can be a rating matrix. That is, $A(i,j)$ is the rating user $i$ has given to item $j$. Suppose that I shuffle the rows and columns of matrix $A$ and get ...
0
votes
0answers
41 views

How can i count the number of flops of the following expression?

lets say, after Cholesky factorization, at some point in my solution I get this: $L_{11}*L_{11}^T=A$, $L_{11}*L_{21}^T=u$, $L_{21}*L_{11}=u^T$, and $L_{21}*L_{21}^T=a$ So, $a$ is a scalar, $u$ and ...
0
votes
1answer
91 views

How can I do this kind of Cholesky decomposition?

$B_{(n+1)(n+1)}$ = $ \begin{bmatrix} A & u \\ u^T & 1 \\ \end{bmatrix}$ = $\begin{bmatrix} L_{11} & 0 \\ L_{21} & l_{22} \\ ...
1
vote
0answers
27 views

how to show cholesky decomposition complexity? [duplicate]

Possible Duplicate: How to calculate the cost of Cholesky decomposition? so far i see that for matrix A = L*L^T : (A = a1, a2, a3, a4 matrix) FOR lower triangular matrix L = l11, 0, L21, ...
6
votes
1answer
399 views

Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?

I have been reading Introduction to Algorithms by Cormen et al. Before explaining Strassen algorithm the book says this: Strassen’s algorithm is not at all obvious. (This might be the biggest ...
2
votes
0answers
113 views

matrix construction

Given any matrix $A$, can one construct a matrix $B$ such that $B$ is nonnegative and the spectral radius of $B$ is strictly less than 1 the determinant of $A$ is equal to the first entry of $B^*$ ...
0
votes
1answer
87 views

A special case of the minimum number of multiplications used to compute a product of matrices

A fact about complexity of algorithms for computing the product of matrices was brought up to me that was very interesting I was not aware of. I still am not sure what the optimal bound is on the ...
3
votes
2answers
388 views

equivalence between matrix multiplication and matrix inversion

I am a bit confused with this wikipedia article, hoping someone can clarify it. Looking at the Strassen algorithm page it is clear that this is an algorithm for reducing multiplication operations. ...
2
votes
1answer
130 views

complexity cost for which one is greater : determinant or eigen values?

what is complexity cost for determining all of eigen values? what is complexity cost for calculating determinant ?
9
votes
2answers
641 views

Has there been a rigorous analysis of Strassen's algorithm?

According to Wikipedia, Strassen's Algorithm runs in $O(N^{2.807})$ time. Has anyone seen a more rigorous analysis displaying constants, possibly in a specific language such as C or Java? I ...
1
vote
1answer
852 views

Gauss Jordan elimination - count of steps for $N \times M$ equation

I am having some problem wrapping my head around an assignment. I have to find out how many additions, subtractions, multiplications and divisions are used while solving an $N \times M$ linear ...