# Questions tagged [linear-algebra]

The tag has no usage guidance.

179 questions
Filter by
Sorted by
Tagged with
729 views

### Suitable choice for moderate-size square matrix multiplication?

The problem is to find $C = AB$, where $A$ and $B$ are $n \times n$ matrices that may be sparse. Let $n$ be around 1000. The elements of $A$ and $B$ are real values, though, for practicality's sake, ...
325 views

### Solving/Optimizing a linear system in a finite field (Z/2Z)

I'm trying to solve the following optimization problem. A is a rectangular matrix with coefficients in the finite field Z/2Z (size less than 1000 X 1000). I have a system of the form A.X = Y (X and Y ...
759 views

### Why linear transformation can improve classification accuracy when the dimensionality of data is high?

Let $X$ be an $m\times n$ ($m$: number of records, and $n$: number of attributes) dataset. When the number of attributes $n$ is large and the dataset $X$ is noisy, classification gets more ...
399 views

### Positive Definiteness Constraint

I want to add a constraint to a convex program, to guarantee some matrix $A$ to be positive semidefinite. How should I do it? The library I am working with can cope with linear/ quadratic ...
98 views

### Gauss-Jordan using stacks and list

I have a homework assignment in which I need to write an implementation of Gauss-Jordan with complete pivoting. Complete pivoting is a modification to the basic Gauss-Jordan algorithm in which rows ...
105 views

### Can this equation be solved in polynomial time?

I came across a more general form of this question. Can we find the value of variables in polynomial time ? Let $m = n^{2}$, there are $m$ variables ($x,y,z\ldots$) in the equation and these $m$ ...
90 views

### Eigenvalue computation for large graph

Consider a large graph, minimum 1 000 vertices but it can easily go up to 50 000 vertices depending the case. The graph is the result of social relationships (followers, following, friendship) so it ...
136 views

### Conditions for Linear Diophantine Equations to always have a solution

Given a set of $n$ linear equations in $v$ integer variables, where $v > n$, we can say that this system of equations will always have an integer solution. Over $\mathbb N$, is there any such ...
199 views

### How to construct a running kd-tree?

I have a stream of 3-tuples of type (x,y,t) where x and y are in the range ...
76 views

### Rank of random binary matrix subset

I have a problem that smells like it is NP-complete, but at the same time it feels like maybe you can solve it by just keeping track of column-wise Hamming distance or something, or that it's ...
2k views

### Efficient computation of Kronecker product

Given matrices $A \in \mathbb{C}^{n_1,m_1}, B \in \mathbb{C}^{n_2,m_2}$ a naive way to computer the Kronecker product would be as such: $M = \operatorname{zeros}(n_1n_2,m_1m_2)$ (initialize an empty ...
3k views

### Machine Learning: how to correctly calculate gradient descent for simple linear problem

So, I was trying to learn machine learning, and, after watching a couple of Andrew Ng's lectures decided to try and write a simple piece of code to determine what someone's salary would be based on ...
3k views

### how to represent Sparse Matrices [closed]

I have been using Harwell Boeing format, also known as Compressed Column Strorage (CCS) in order to store Sparse Matrices. Could you please suggest me some other way to store/represent sparse ...
737 views

### Counting solutions to system of linear equations modulo prime

I have implemented Gaussian elimination for solving system of linear equations in the field of modulo prime remainders. If there is a pivot equal to zero I assume the system has no solution but how to ...
92 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. ...
683 views

### Finding the bandwidth of a band matrix

I am designing an algorithm that solves a linear system using the QR factorization, and the matrices I am dealing with are sparse and very large ($6000 \times 6000$). In order to improve the ...
231 views

### Count number of linearly independent subsets of columns of a binary matrix

I have a binary $m \times n$ matrix of rank $m$ (hence $m < n$). I need to count how many subsets of its columns form matrices with a full column rank, i.e. columns in the subset are linearly ...
211 views

### Derandomization of an approximation algorithm for solving a linear system

I was given a HW assignment that asks me the following: Given a system of $m$ linear equations in variables $x_1,x_2,...,x_n$ over $\mathbb{F_p}$, find a randomized algorithm that find an assignment ...
207 views

### Devising an Algorithm for Linear Combination with Column Restrictions

Application: We intend to factor an integer $N$ using a variation of the rational sieve. This involves constructing a congruence of squares modulo $N$ from a set of linear relations $$x - N = y$$ ...
65 views

### Generalized operators for programming languages

After asking this question on stackoverflow, it has changed slightly. Is there a way to represent a grammar as a basis for a vector space and represent a program as an object that lives in that ...
52 views

### Heuristic for making set of indexes in an array/matrix with generating functions/patterns

I am trying to find a lead on how to solve or find a heuristic the following kind of problem: Given an array/matrix with entries of only 1s and 0s, using a set of looping functions/patterns of a ...
952 views

### Does PETSc really give speedup?

I searched linear solver library and found out PETSc library which considered to be powerful and useful library. PETSc consists implementations of various iterative methods with preconditioners and ...
200 views

77 views

### Vandermonde matrix and its binary representation

Say one is given a Vandermonde matrix (https://en.wikipedia.org/wiki/Vandermonde_matrix) of dimension $2^q \times k$ such that the elements of the first column of it are $\{0,1,2,..,-1+2^q\}$. (This ...
I am trying to implement a fast SVD algorithm for obtaining the first $k$ singular values/vectors of an $M\times N$ matrix ($k < \min(M,N)$) using the following 2-step process: 1) bidiagonalize ...
Is there an efficient algorithm for the following problem? Given: a $m$-vector $b \in \{0,1,2\}^m$, and a $m \times 2m$ matrix $A$, with the promise that for every $b' \in \{0,1,2\}^m$, there exists \$...