1
vote
0answers
51 views

Finding special vectors generated by a matrix

Let $G\in \Bbb Z^{n\times n}$ be a unimodular matrix. Are there any efficient algorithms to find the maximum norm of a vector $v$ that satisfies $\langle\Delta(v),v\rangle=0$ over all vectors $v\in ...
3
votes
0answers
158 views

Beating Kadane's Algorithm

I am seeking some reference on already existing work for the following problem. Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...
5
votes
0answers
321 views

Determine if a matrix is unimodular

Is deciding if an integer square matrix has determinant $\pm 1$ faster that calculating the determinant of the matrix?
16
votes
1answer
2k views

How fast can we *really* multiply matrices?

Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.8})$ for the multiplication of two $n \times n$ matrices. However, the constant is so large that ...
2
votes
1answer
409 views

Does a product of matrices have eigenvalue 1

Start by fixing invertible matrics $A_1, \ldots, A_m \in \mathbb{Z}^{n \times n}$. For a sequence $i_1, \ldots, i_k$ we construct $A = A_{i_1} \cdots A_{i_k}$. We would like to know "Is 1 an ...
5
votes
2answers
402 views

Complexity of Membership-Testing for finite abelian groups

Consider the following abelian-subgroup membership-testing problem. Inputs: A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with ...
0
votes
1answer
793 views

True divide and conquer inversion of large matrices

In http://math.stackexchange.com/questions/2735/solving-very-large-matrices-in-pieces there is a way shown to solve matrix inversion in pieces. Is it possible to turn it into a true divide and conquer ...
7
votes
5answers
1k views

Strassen Algorithm 7 multiplications

Strassen Algoritm is a well-known matrix multiplication divide and conquer algorithm. The trick of the algorithm is reducing the number of multiplications to 7 instead of 8. I was wondering, can we ...
3
votes
1answer
224 views

Finding a 5-cycle in a sparse graph efficiently.

Hi, I was reading this thread: Finding a cycle of fixed length I want to find a 5-cycle in a graph. Actually, what I really want is a shortest odd cycle of length at least 5, but maybe that is a ...
1
vote
1answer
1k views

Bidiagonalization and SVD of matrix

I can't find a single solid explanation of how to implement this -- whitepapers too detailed/confusing. Closest I came to an answer was this: ...
1
vote
5answers
2k views

Nodes clusters with a distance matrix

Hi, I have a (symmetric) matrix $M$ that represents the distance between each pair of nodes. For example, A B C D E F G H I J K L A 0 20 20 20 40 60 60 60 100 120 ...
2
votes
2answers
328 views

Efficient computation of AB^-1 for matrices

Hi there, Sorry if this has already been asked before. I tried googling for it, but perhaps I could not find the right words to search for. My question is: Which is the fastest way to compute ...
2
votes
1answer
614 views

Condition number for Ellipsoid method matrix

Hello, When using the ellipsoid method (for solving a linear program for example), the volume of the ellipsoid at each iteration is proven to decrease, and do so by at least a factor of $e^{1/2n}$. ...
2
votes
1answer
1k views

Matrix approximation

Let A be an $m\times n$ matrix and $k$ be an integer. Assume that $A$ is non-negative. We want to find a scalar $\epsilon$ and an $n\times n$ matrix $B$ such that $A\leq A(\epsilon I + B)$ (where ...
8
votes
2answers
2k views

What is the constant of the Coppersmith-Winograd matrix multiplication algorithm

Or at least it's order of magnitude. I've only ever heard it described as "huge", and a google search turned up nothing. Also, given that the Strassen algorithm has a significantly greater constant ...