The linear-algebra tag has no wiki summary.
3
votes
0answers
38 views
how to represent Sparse Matrices
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 ...
1
vote
2answers
62 views
Finding the required value of an algebric expression
I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.
I want to find the ...
2
votes
3answers
30 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. ...
4
votes
2answers
78 views
Can you complete a basis in polynomial time?
Here is the problem: we are given vectors $v_1, \ldots, v_k$ lying in $\mathbb{R}^n$ which are orthogonal. We assume that the entries of $v_i$ are rational, with numerator and denominator taking $K$ ...
3
votes
1answer
41 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 ...
1
vote
2answers
95 views
What is the complexity of this matrix transposition?
I'm working on some exercises regarding graph theory and complexity.
Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically ...
0
votes
0answers
28 views
multigrid method to solve PDE [closed]
I need explanation of the Multigrid Method or some literature.
I am familiar with iterational methods including BiCGStab,CG,GS,Jacobi and preconditioning, but I am a beginner with multigrid method.
...
2
votes
1answer
46 views
LU decomposition with pivoting
I have to solve system of linear algebraic equations $AX=B$, where $A$ is a two-dimensional matrix with all elements of main diagonal equal to zero.
How to solve this problem? Iterational methods are ...
3
votes
1answer
121 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 ...
2
votes
0answers
22 views
Maximum feasible subsystem problem (MaxFS) in 2 variables
Topic:
The maximum feasible subsystem problem, which is generally NP-hard [1].
Question:
Are there special algorithms in case of only 2 variables (2D linear constraints)? The problem seems to be a ...
7
votes
0answers
103 views
Alternatives to SVD for rank factorization
I have rank-deficient matrix $M \in \mathbb{R}^{n\times m}$ with $\text{rank}(M) = k$ and I want to find a rank factorization $M = PQ$ with $P \in \mathbb{R}^{n \times k}$ and $Q \in \mathbb{R}^{k ...
2
votes
0answers
40 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 ...
6
votes
1answer
117 views
Probabilistic test of matrix multiplication with one-sided error
Given three matrices $A, B,C \in \mathbb{Z}^{n \times n}$ we want to test whether $AB \neq C$. Assume that the arithmetic operations $+$ and $-$ take constant time when applied to numbers from ...
7
votes
1answer
352 views
Complexity of checking whether linear equations have a positive solution
Consider a system of linear equations $Ax=0$, where $A$ is a $n\times n$ matrix with rational entries. Assume that the rank of $A$ is $<n$. What is the complexiy to check
whether it has a solution ...
