The tag has no usage guidance.

learn more… | top users | synonyms

3
votes
2answers
111 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 ...
4
votes
1answer
46 views

Number of solutions to linear system of equations over GF(2)

Linear systems of equations over the reals have either 0, 1 or infinitely many solutions. However, when applied to finite fields (specifically GF(2)), infinitely many is not an option. Is there a ...
1
vote
1answer
56 views

Scheduling distributed computational graph

I work in computational fluid dynamics. And I spend most of my time waiting for simulation to complete. The common way to improve simulation performance is to use a suitable distributed linear ...
5
votes
0answers
47 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 ...
1
vote
0answers
20 views

2 qubits, correct way CNOT a 3rd qubit with the 1st? [duplicate]

Suppose I have 2 qubits in the state a|00>+b|01>+c|10>+d|11>. And suppose I want to perform some operation between only the 1st qubit and a 3rd qubit - for example a CNOT operation. What would be ...
4
votes
1answer
50 views

Unfeasible linear program becomes feasible if a variable is removed

Apologies, not a computer scientist by trade but I'm playing with linear programming these days. Let $\{x_i\}$ be $N$ optimization variables with bounds $$l_i \leq x_i \leq u_i$$ I'm interested in ...
4
votes
1answer
32 views

Efficient algorithms for dealing with linear algebra over the rationals

I'm an academic mathematician. While trying to verify a counterexample to something in my research, the following computational problem has arisen: Fix a vector space $V = \mathbb{Q}^n$. Here $n$ ...
1
vote
0answers
19 views

Matrix whose eigenvectors are Hermite polynomials [closed]

I first constructed a symmetric matrix as the Laplacian operator, and its eigenvectors are a series of harmonics functions as expected. I programmed it and convinced myself. The matrix looks like: $$ ...
16
votes
4answers
379 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, ...
0
votes
1answer
37 views

Algorithm for projection of polytope

Let a convex bounded polytope be given by an intersection of half planes: $Ax \leq b$. Let $z=Cx$ be a vector (in my case $z$ is 2-dimensional, while $x$ has a higher dimension). How can I compute ...
0
votes
0answers
37 views

Most stable algorithm to solve a system of linear equations?

I am doing some image processing involving solving a system of linear equations. I am getting some errors and bits of the image looks corrupted. I would like to know what is the most stable way to ...
3
votes
1answer
73 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$$ ...
2
votes
1answer
81 views

Intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem using as little matrices/linear algebra as possible?

could someone provide me/refer me to a intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem that uses as little technical details involving matrices/linear algebra as possible? I'm trying to ...
6
votes
1answer
96 views

Are there any non-naive parallel sparse matrix multiplication algorithms?

I was wondering about a problem in analyzing a social network (counting friends-in-common between all pairs of members) that requires squaring its adjacency matrix, and started reading up on ...
4
votes
1answer
62 views

solving large nonlinear systems in parallel

I am solving a large (~1e5 equations & unknowns) set of nonlinear equations using Newton-Raphson iterations. Currently I am using the GPU accelerated Krylov methods implemented in ViennaCL to ...
1
vote
1answer
24 views

Minimise simultaneous equation remainder

I'm not sure if this is the right place to ask, or what the right terminology to use is. The problem I have is this: I have a vector for example: v = [1,4,5,6,3,1,4,5,6,7,...7] and I have a set of ...
1
vote
0answers
67 views

Comparison of matrix determinant in less than $O(n^2)$

I was reading this question and I think maybe somebody here could help. This is the idea: Given a matrix $M$ of integers, and a number $d$ is there a way to compare the determinant of $M$ and $d$ in ...
2
votes
1answer
372 views

How to solve a Simple Linear Equation using a binary tree data structure

i am currently working on a school project that takes in a simple linear equation and has to return the value of x, the code i have transforms x + 3 = 3x - 2 into a binary tree format like so: ...
0
votes
0answers
31 views

Integer linear program for Ising ground state problem

I am trying to model the Ising spin state problem into Integer linear program and find the optimal ground state using lp_solve. (This is just a miniature version of Ising state problem) $$ maximise: ...
1
vote
1answer
33 views

Creating a single layer perceptron for the OR problem

I am working on the following problem Find the linear least squares unit weights for the `OR' problem, ie. $v_1^T = (0,0), v_2^T = (1,0), v_3^T = (0,1), v_4^T = (1,1)$ and $u_1 = 0, u_2 = u_3 = u_4 = ...
10
votes
5answers
2k 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 ...
1
vote
1answer
44 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 ...
0
votes
1answer
35 views

What is the exact definition of a dictionary in the concept of linear algebra and computer science?

I am reading this paper for my master thesis and trying to understand every concept in it. The following sentence confuses me as to what is the exact definition of a dictionary in this concept except ...
8
votes
1answer
111 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 ...
0
votes
0answers
30 views

Partially diagonalizing a matrix

Suppose I have a $n\times n$ matrix. I would like to keep an $m\times m$ subblock undiagonized, while keeping the rest diagonized. Is there any algorithm for this? More precise, I mean using unitary ...
1
vote
1answer
66 views

Feasibility of linear inequalities with binomial variables

I have a system of linear inequalities of the form $A^t x <= b$ where each of the $x_i$'s is a binary variable in $\{0, 1\}$. Are there any known fast and practical algorithms that can find a ...
5
votes
1answer
122 views

Complexity of Pythagorean triples

We define a Pythagorean triple as a triple $\langle a,b,c\rangle$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$. In order to avoid duplicates, we say that a triple $\langle a,b,c\rangle$ is legit ...
4
votes
2answers
444 views

Proof of Strong Duality Via Farkas Lemma

I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the ...
6
votes
1answer
222 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 ...
0
votes
1answer
145 views

How to use different size features in SVM?

I want to train a support vector machine with some features. The problem is, one of the features is 1-dimensional (only an angle) and the other is an LBP Histogram, an 58-dimensional vector. ...
6
votes
1answer
117 views

Does spectral graph theory say anything about graph isomorphism

Is there research or are there results that discuss graph isomorphism in the context of spectral graph theory? Two known theorems of spectral graph theory are: Two graphs are called isospectral or ...
2
votes
1answer
34 views

Subspace clustering with random transformation

One approach for clustering a high dimensional dataset is to use linear transformation, and the most common approaches are PCA and random projection (where random projection arises from the ...
3
votes
1answer
161 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 ...
8
votes
1answer
840 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. ...
4
votes
1answer
104 views

How to compute a curious inverse

Let $M$ be a square matrix with entries that are $0$ or $1$ and let $v$ be a vector with values that are also $0$ or $1$. If we are given $M$ and $y = Mv$, we can computer $v$ if $M$ is non-singular. ...
2
votes
0answers
34 views

Solution of a Toepltiz system of linear equations

I want to code a solver for nonsingular systems of $N$ linear equations in $N$ unknowns (say up to $N=100$) with an asymmetric Toeplitz matrix. I know that the Levinson algorithm can solve it in time ...
2
votes
1answer
163 views

Power method to calculate eigenvectors

I've implemented a program for computing eigenvectors of some random, symmetric, $N$x$N$ matrix using the power method. I have found difficulty in calculating all $N$ eigenvectors consistently, ...
2
votes
1answer
30 views

Solving for the matrix $W$ in an equation involving $W \cdot W^{T}$

Having large matrices, $W$ (the unknown) and $M$ (known), is it possible to solve for $W$ in this equation $$W \cdot W^{T} = M,$$ where $M$ can have negative entries.
1
vote
1answer
78 views

Calculating eigenvalue gap of a torus graph

Consider a two-dimensional grid with wrap-around edges (a doughnut-shaped graph). I need to calculate the second-largest eigenvalue of the adjacency matrix. Is there a faster way of computing it for ...
5
votes
2answers
252 views

Find a binary matrix so that no vector from {-1,0,1}^n is in its kernel

Given integers $n,m$, I want to find a $m \times n$ binary matrix $X$ such that there does not exist any non-zero vector $y \in \{-1,0,1\}^n$ with $Xy=0$ (all operations performed over $\mathbb{Z}$). ...
6
votes
1answer
216 views

Testing whether a determinant polynomial is identically zero

Suppose we are given matrices $A_1, \ldots, A_k$ which are $n \times n$ matrices with rational entries and are asked to determine whether the polynomial ${\rm det}(\alpha_1 A_1 + \alpha_2 A_2 + \cdots ...
7
votes
1answer
1k views

Short and slick proof of the strong duality theorem for linear programming

Consider the linear programs \begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array} \begin{array}{|ccc|} \hline Dual: & ...
0
votes
1answer
69 views

Solving a graph problem by Gaussian elimination

I have been given a graph with n nodes. Now, I have to color every node of this graph by k colors, number from 0 to k-1. Now, there is a rule. For a node $x$ with adjacent nodes $y_1 , y_2, y_3, ...
3
votes
1answer
58 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 ...
4
votes
1answer
198 views

What are some applications of computing the permanent of a matrix?

What are some applications that require computing the permanent of a matrix? One application I know of is related to graph theory and matchings. Apparently, the number of perfect matchings of a ...
5
votes
1answer
257 views

Comparing sets of vectors

If $u,v \in \mathbb{R}^d$ are two $d$-dimensional vectors, say that $u\le v$ if $u_i \le v_i$ for all $i=1,\dots,d$. In other words, comparisons on vectors will be pointwise. Let $S,T$ be two ...
4
votes
1answer
2k views

Checking Feasibility of Linear Program in Polynomial Time

Given a linear system of the form: $$\begin{array}{c} x_r = a \quad x_j = b \\ c_1x_1 + c_2x_2 + \ldots + c_nx_n = N \\ x_1+x_2 + x_3 + \ldots + x_n = k\\ 0 \le a,b,x_1,x_2,x_3...x_n \le 1\\ k \ge 0 ...
1
vote
0answers
38 views

Laplace's Approximation for graphical models

A question about Laplace's approximation: In Laplace's method, we need to find the mode of a function and take second order Taylor's expansion. The first order term will vanish (since the gradient is ...
1
vote
1answer
188 views

Significance of parameters in Tiny Mersenne Twister algorithm

I am trying to implement and optimize the Tiny Mersenne Twister (TinyMT) algorithm as required by an API I am developing with my team at work. The algorithm utilizes a C structure with 32-bit unsigned ...
1
vote
0answers
33 views

Is this problem in P: Finding a common key for a collection of systems of equations?

Let $B=\{b_1=g_1,\cdots,b_n=g_n\}$ be a set of binary variables $b_i$ and their corresponding values $g_i \in \{0,1\}$. Let $M=\{\sum_{e \in A}e \;:\; A \subset B\}$, i.e., $M$ is the set of all ...