12
Consider the problem $\text{MAX-LIN}(R)$ of maximizing the number of satisfied linear equations over some ring $R$, which is often NP-hard, for example in the case $R=\mathbb{Z}$
Take an instance of this problem, $Ax=b$ where $A$ is a $n\times m$ matrix. Let $k=m+1$. Construct a new linear system $\tilde{A}\tilde{x} = \tilde{b}$, where $\tilde{A}$ is a $kn ...
7
The following article discusses various approaches to reducing the bandwidth of unsymmetric matrices.
J.K. Reid, J. A. Scott: Reducing the total bandwidth of a sparse unsymmetric matrix, SIAM Journal on Matrix Analysis and Applications 28(3):805–821.
The technical report version of the article is available here:
J. K. Reid and J. A. Scott, Reducing ...
6
The problem is NP-complete, by reduction from the following problem:
Given an $m\times n$ matrix $A$ with integer entries and an integer vector $b$ with $n$ entries, does there exist a 0-1 vector $x$ with $Ax=b$?
For every coordinate $x_i$ of vector $x$,
introduce $100(n+m)$ new equations $x_i+y_{i,k}=0$ with $k=1,\ldots,100(n+m)$, and
introduce $100(...
6
Depends how you feel about the exponent of matrix multiplication, as this would come very close to showing $\omega=2$.
If the answer to your question were positive, then you could compute the determinant of an arbitrary symmetric $n \times n$ $\{0,1\}$ matrix $M$ (=adjacency matrix of an undirected graph, possibly with self-loops) in $O(n^2)$ time. As the ...
4
The Faddeev-Leverrier algorithm seems to be a good start to answer your question, since it reduces the computation of $\alpha_k$ to matrix multiplications and traces. It runs in polynomial time (even in NC) and I guess any efficient treatment of sparse matrix operation carries to this algorithm.
Oddly enough the wikipedia page about that exists only in ...
4
This is called the Sparsest Solution Vector problem, and it is indeed NP-hard.
4
This problem is hard, in various settings. As stated in the other answers to this question, the problem is NP-complete over the integers.
In signal processing, the matrix and the vectors have rational entries, and this problem is sometimes called the sparse reconstruction problem. In this setting, the problem is NP-complete (see Theorem 1).
In coding ...
3
It's a good question. You can use a Laplacian solver if $A$ is symmetric and diagonally semi-dominant (SDD). This is the subject of Theorem 9.2 in your reference book from Vishnoi. A good exposition of the proof (which was originally by Gremban) can be found in Appendix A of the paper by Kelner, Orecchia, Sidford and Zhu (arXiv:1301.6628).
A recent result by ...
2
Jacobi or Gauss-Seidel are not really state of the art for solving systems of linear equations. It is more done by preconditioned conjugated gradient (for symmetric positive semi-definite matrices) and preconditioned (F)GMRES (or other Krylov subspace methods) for arbitrary matrices.
The crucial part here is the preconditioner. There was recently (=21th ...
2
In the proof of theorem 2 in Improved Approximation Algorithms for Rectangle Tiling and Packing by Berman et al, they proved an upper bound of $\frac{11}{5} \max\{W/p,y\}$, where $W$ is the sum of the weight of all elements, $p$ is the number of rectangles and $y$ is the weight of the largest element.
This implies a upper bound of $\frac{11}{5j}$ for your ...
1
Consider a real world 'signal' - a discrete set of numbers representing something real (e.g. an image, an audio recording, etc.). These numbers form a vector in some vector space. Any such vector can be transformed into many different bases. The vector will be more 'sparse' in some of those bases than others. In fact, there's even a set of bases where the ...
Only top voted, non community-wiki answers of a minimum length are eligible
