All Questions
9 questions with no upvoted or accepted answers
11
votes
0
answers
764
views
Fast computation of matrix product $AXA^T$ with fixed $A$?
Suppose we have two $n$-by-$n$ matrices $X$ and $A$, where $A$ is known and $X$ may change in different invocations, and we want to compute $AXA^T$. Is there an algorithm that beats the naive one of ...
- 75
3
votes
0
answers
148
views
Linear combinations of special matrices
I am a hobby computer scientist and I have a problem to which I am searching an efficient algorithm.
Given an integer n, we want to combine some square input-matrices of size n in a way that is ...
- 73
2
votes
1
answer
456
views
Integrality certification for product of two matrices $A B^{-1}$
Let's consider two non-singular integer matrices $A,B \in\mathbb{Z}^{n\times n}$. I want a test to check if $A\times B^{-1}$ is integral (or no denominators). I am referring the unimodular ...
- 149
1
vote
0
answers
138
views
Questions on integer matrix multiplication
Question 1:
Given two integer matrices $A$ and $B$, and let $C$ be $AB$.
$C$ can be very big in pratice, so what is the fastest way to compute the statistical data of $C$?
For example,
$$A=\begin{...
- 696
1
vote
0
answers
35
views
Are there any known lower complexity bounds on solving positive semidefinite or positive semidefinite feasibility problems?
I've been trying to attack the problem posted here, about quickly checking if a matrix has any positive semidefinite completions. I suspect that the answer to the question is "no", because ...
- 111
1
vote
0
answers
121
views
Algorithm for the nilpotence of matrix polynomials
Let $P$ be a multivariate polynomial of real-valued $N \times N$ matrices. Given $X_1, X_2, ..., X_M \in \mathcal{M}_N\{\mathbb{R}\}$, is there any optimal algorithm to determine whether the result of ...
- 19
1
vote
0
answers
174
views
Approximating symmetric matrices by symmetrized low rank matrices
Fix an integer $k$, and suppose $M$ is a real symmetric $n\times n$ matrix admitting a decomposition:
$$
M = A + A^t + B
$$
with $\mathrm{rank}(A)=k$ and:
$$
\|B\|_2 \ll \lambda_{1}(M_{|\mathrm{range}(...
- 121
1
vote
0
answers
128
views
How to efficiently evaluate the action form of a matrix power?
Binary exponentiation is a well-known method for evaluating positive integer powers of a matrix, $A^p, \; A\in\mathbb C^{n\times n},\,p\in\mathbb Z^+$.
However, I am not seeing an obvious way to ...
- 19
1
vote
0
answers
114
views
Intersecting vector spaces defined over different fields
Let $K_1, K_2$ be subfields of $K$, let $k = K_1 \bigcap K_2$, let $V_1$ be a $K_1$-vector space, $V_2$ be a $K_2$-vector space, both of them subsets of a $K$-vector space $V$.
How can I compute a $k$...
- 314