8
votes
1answer
457 views

How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?

Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that $n = \sum_{i=1}^k a_i m_i$? ...
7
votes
1answer
212 views

Main problems on lattice-basis reduction algorithms (such as LLL)?

What are the main open problems on lattice-basis reduction algorithms (such as LLL)? I am looking for problems satisfying the following two conditions: (a) their solution would likely be of some ...
3
votes
1answer
126 views

Question about the elementary divisors of a special matrix

I have the following question: Is there a closed formula for the elementary divisors of the Matrix $M=\lbrace (m_{ij})\rbrace_{i=1,...,n,\ j=1,...,k}$, where $m_{ij}$ is the greatest common ...
0
votes
1answer
193 views

Deriving the fundamental equation (with regards to computer vision)

I'm having a hard time understanding how a few equations are being derived. So the fundamental equation is an equation that relates corresponding points in stereo images. Anyway, that's the basic ...
5
votes
6answers
2k views

Fast evaluation of polynomials

Hello everybody ! I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...
2
votes
0answers
212 views

what is the largest gap between rank and approximate rank

$\epsilon$-approximation rank of a matrix $M$ is the minimum rank of a real matrix $A$ which differs from $M$ at most $\epsilon$ in each entry. Associating any function $f:X\times Y\rightarrow${1,-1} ...
1
vote
0answers
727 views

Lambert's Cosine Law - Simple algebraic rearrangement problem [closed]

Let $I(x,y)$ be the intensity at position $(x,y)$, $\rho(x,y)$ be the albedo at this point (a constant), $n=(p,q,1)$ be the surface gradient vector and $s_{0},s_{1},s_{2}$ all be vectors from the ...
3
votes
2answers
321 views

Finding the solution to b = Ax that minimizes the Hamming weight (everything over the field F_2).

Is there an efficient algorithm for finding the solution $x$ of $b = Ax$ that minimizes the Hamming weight of $x$, where $A$ is a nxm-matrix over the field $\mathbb{F}_2$ ("integer matrix modulo ...
2
votes
0answers
252 views

Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
2
votes
1answer
1k views

Conditions that allow unique solutions for Linear Diophantine equations

(This posting became very long, so I should note that there are two alternative but nearly equivalent formulations of the same question being given. The first one asks for the optimal strategy for ...
1
vote
1answer
188 views

Extracting integer multiplicative factors from the sum of certain sets of (finite-precision) real numbers?

Update based on Michael's answer (thanks again!) - Can the LLL or PSLQ algorithms provide a (knowably - i.e. not just incidental) unique solution for the set of integer multiplicative factors? Are ...
11
votes
2answers
2k views

How to compute the rank of a matrix?

Okay, that's a misleading title. This is a somewhat subtler problem than undergraduate linear algebra, although I suspect there's still an easy answer. But I couldn't resist :D. Here's the actual ...