# Tagged Questions

**1**

vote

**0**answers

52 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

**0**answers

173 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

**0**answers

337 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?

**17**

votes

**1**answer

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 ...

**3**

votes

**1**answer

416 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

**2**answers

415 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

**1**answer

873 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

**5**answers

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

**1**answer

228 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

**1**answer

2k 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

**5**answers

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

**2**answers

331 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

**1**answer

624 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

**1**answer

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 ...

**9**

votes

**2**answers

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 ...