0
votes
0answers
6 views

Lowest complexity matrix multiplication using parallelization

I'm not very familiar with complexity calculations (though I'm trying to learn), but what is the fastest published way to multiply two square matrices together with a GPU? The estimate I can come up ...
11
votes
3answers
296 views

Eigenvalue test faster than $O\left(n^3\right)$?

Given a real $n\times n$ matrix $A$, one can find the eigenvalues in $O\left(n^3\right)$ by using say, the $QR$ algorithm. Now, what if we guess an eigenvalue $\lambda_0$, and we want to know if it's ...
11
votes
3answers
167 views

Is there an easy way to find the sign of the determinant of an orthogonal matrix?

I just learned that if a matrix is orthogonal, its determinant can only be valued 1 or -1. Now, if I were presented with a large matrix where it would take a lot of effort to calculate its ...
1
vote
0answers
26 views

Is finding a matrix out of some set with a given determinant a hard problem?

Given $n\ge 2\ \ ,\ u,v,k\ $ integers. Decision problem : Does a $n\times n$ - matrix with entries from $u$ to $v$ with determinant $k$ exist? In which complexity class is this problem ? Is it ...
1
vote
2answers
37 views

Is factoring a semiprime easier than matrix multiplication?

I'm currently dealing with complexity estimates of various algorithms and the connected mathematical problems. Up until now, I had in mind that problems such as integer factorization and the discrete ...
1
vote
0answers
50 views

Fast checking Matrix multiplication in mod 10

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In ...
1
vote
1answer
140 views

Tree Traversal - Simple Puzzle type Issue.

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...
0
votes
0answers
35 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
66 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
340 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
364 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
119 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
223 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
183 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
720 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
218 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
88 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
93 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
427 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
89 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
416 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
131 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
653 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
891 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 ...