# Questions tagged [linear-algebra]

The tag has no usage guidance.

173 questions
Filter by
Sorted by
Tagged with
4answers
972 views

### Automated optimization of 0-1 matrix vector multiplication

Question: Is there established procedure or theory for generating code that efficiently applies a matrix-vector multiplication, when the matrix is dense and filled with only zeros and ones? Ideally, ...
5answers
5k views

### What parts of linear algebra are used in computer science?

I've been reading Linear Algebra and its Applications to help understand computer science material (mainly machine learning), but I'm concerned that a lot of the information isn't useful to CS. For ...
1answer
4k views

### Complexity of finding the pseudoinverse matrix

How many arithmetic operations are required to find a Moore–Penrose pseudoinverse matrix of a arbitrary field? If the matrix is invertible and complex valued, then it's just the inverse. Finding ...
2answers
564 views

1answer
362 views

### What algorithms exist for solving natural number linear systems?

I'm looking at the following problem: Given $n$-dimensional vectors of natural numbers $v_1, \ldots, v_m$ and some input vector $u$, is $u$ a linear combination of the $v_i$'s with natural number ...
3answers
3k views

### Fastest way to solve a system of linear equations

I have to solve a system of up to 10000 equations with 10000 unknowns as fast as possible (preferably within a few seconds). I know that Gaussian elimination is too slow for that, so what algorithm is ...
1answer
602 views

### Minimal basis for set of binary vectors using XOR

I would be surprised if this isn't a well-studied problem, but I'm not sure what else to search for at this point: you're given a set of binary $n$-vectors $S \subset \{0,1\}^n$. The problem is to ...
2answers
737 views

### Could a quantum computer perform linear algebra faster than a classical computer?

Supposing we had a quantum computer with a sufficient number of qubits, could we use it to do linear algebra faster than we could with a classical computer? What sort of speedup could we expect? Has ...
1answer
889 views

### Inverting a band matrix

I have a band matrix -- a sparse, square, symmetric $N \times N$ matrix whose structure looks like the following: Here, the area under the blue stripes is the non-zero elements; everything else is ...
1answer
266 views

### Generate algorithmically all grid points inside a hypercube

$\def\R{\mathbb{R}}\def\Z{\mathbb{Z}}\def\n#1{\|#1\|_\infty}$The problem comes directly from computational mathematics, and can be stated as follows: Given a regular matrix $M\in\R^{d\times d}$, find ...
1answer
1k views

4answers
3k views

### Solving system of linear inequalities

I am trying to solve a system of inequalities in the following form: $\ x_i - x_j \leq w$ I know these inequalities can be solved using Bellman-Ford algorithm. ...
1answer
7k views

1answer
69 views

### Interpreting camera matrix

I'm having some trouble interpreting the camera matrix $K = \begin{bmatrix} f_x & s & x_0 \\ 0 & f_y & y_0 \\ 0 & 0 & 1 \end{bmatrix}$ after it multiplies some 3D vector. ...
1answer
162 views

### Time - Complexity Convex Optimization and Eigen Decomposition

Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be? Is the ...
0answers
117 views

0answers
154 views

### Intuitive self-contained proof of Farkas' Lemma

I've been studying the proof of Farkas' Lemma, and given my rather fuzzy memory of Linear Algebra, am having some trouble with it. One version of Farkas' lemma states: For any convex cone generated ...