27
votes
Is there a fast way to check if a matrix has any small eigenvalues?
Are you interested in a clever algorithm, or do you just want to get the answer fast?
If the latter, then I would suggest the following:
Use an established off-the-shelf eigenvalue solver.
Vectorize ...
- 1,160
20
votes
Is there a fast way to check if a matrix has any small eigenvalues?
I am not sure if this is going to be faster than what you are doing now (which is already a clever method), but you can try the following.
Compute $B = A^{-1}$. We know that $A$ has an eigenvalue in $...
- 20.2k
20
votes
How to speed up the process for calculating the Groebner basis?
In this case, because the equations have a lot of structure, you are better off using the structure than using a brute force tool such as Gröbner bases. (Unless this is just an exercise to help you ...
- 108k
17
votes
Background for the Elkies-Klagsbrun curve of rank 29
With regard to question 3:
In earlier work, specifically the paper "New rank records for elliptic curves having rational torsion", the same authors, Elkies and Klagsbrun, attained new ...
- 148k
16
votes
Accepted
simple conjecture on palindromes in base 10
Using
$$\frac{10^c-1}{9}=\sum_{m=0}^{c-1} 10^m,$$
the product in question equals
$$\sum_{n=0}^{2a+2b+c-1}r(n)10^n,$$
where $r(n)$ is the number of times $n$ occurs among the numbers (counted with ...
- 105k
14
votes
Is there a fast way to check if a matrix has any small eigenvalues?
A symmetric matrix $A$ has an eigenvalue in $(-1,1)$ iff $A^2$ has an eigenvalue in $[0,1]$. Equivalently this means that
$$
\min_{\Vert v\Vert=1} \frac{\Vert Av\Vert^2}{\Vert v\Vert^2} <1.
$$
...
- 34.7k
10
votes
Is there a fast way to check if a matrix has any small eigenvalues?
This subtle question requires subtle answers. To begin with, let me discard a few strategies that seem erroneous when the matrices $A\in{\bf Sym}_n$ have a very large size $n$.
Random sampling: ...
- 52.3k
10
votes
Accepted
Is there an equivalent of the incompleteness theorems/halting problem in category theory?
There is a category theoretic version of the incompleteness theorem originally due to André Joyal that has been unavailable for a long time, but has been written up not so long ago by Joost van Dijk ...
- 42.4k
9
votes
How to speed up the process for calculating the Groebner basis?
I am no expert in Groebner bases and can't give any insight as to why one method works and another doesn't. But using SAGE with the code
...
- 91
9
votes
Accepted
Software for recognizing algebraic or D-finite formal power series
Fricas is good at that. It can be accessed via sage, once installed.
...
- 3,587
8
votes
Accepted
Conjecture on palindromic numbers
The conjecture is true.
Let $b=a(n)=2^n+1$.
First, notice that the number in question is
$$N=(b^c-1)\frac{b^{m_1}+1}2\cdots \frac{b^{m_n}+1}2 = \frac{b^c-1}{b-1}(b^{m_1}+1)\cdots (b^{m_n}+1).$$
...
- 34.3k
8
votes
Background for the Elkies-Klagsbrun curve of rank 29
The announcement on the NMBRTHRY listserv seems by Noam Elkies seems worth reproducing here.
The elliptic curve
$$E29 :y^2 + xy = x^3 - 27006183241630922218434652145297453784768054621836357954737385 ...
5
votes
Important open problems that have already been reduced to a finite but infeasible amount of computation
Is there always a prime in the interval $(x^3,(x+1)^3]$ for every natural number $x\geq 2$?
Equivalently the interval may be changed to $[x^3,(x+1)^3]$. Assuming the Riemann hypothesis, this is ...
5
votes
Important open problems that have already been reduced to a finite but infeasible amount of computation
It is thought that it is more difficult to calculate the permanent of an $n\times n$ matrix than to calculate the determinant of the matrix.
However, even for $4\times 4$ matrices this problem seems ...
5
votes
How to recover integer part from known fractional root part?
Using the structure in the continued fraction expansion of a square root provides a relatively straightforward approach: expand out the continued fraction of $f$ until you see an initial segment that ...
- 1,951
4
votes
How to speed up the process for calculating the Groebner basis?
As suggested by Michael Seifert,
...
- 3,486
4
votes
Is there a fast way to check if a matrix has any small eigenvalues?
You can check if the matrix $$A^T A - I$$ is positive definite. This can be done with Cholesky Decomposition, which runs in time $O(n^3)$ and fails for non-positive-definite matrices.
If $A^TA -I$ is ...
- 695
4
votes
Accepted
Conjecture that relates matrix systems with some polynomials of integer coefficients as solution sets
Let me denote $u_i = x^{i+1} + 1$. As I learned from the previous question, under the "matrix system" OP understands the following matrix equation (up to a factor $\frac{1}{x}$):
$$My = b,$$
where
$$M:...
- 34.3k
4
votes
Accepted
Problem on triangles
The equality is never satisfied.
We send $T$ to $T^t$ by an affine map. This sends the unit circle to an ellipse. The bilipschitz constant is either the half of the major axis or the reciprocal of ...
- 6,337
3
votes
Important open problems that have already been reduced to a finite but infeasible amount of computation
At the turn of the 21st century, Catalan's conjecture that $8$ and $9$ are the only non-trivial consecutive powers was reduced to a finite but intractable problem.
For example, it was known that ...
3
votes
Background for the Elkies-Klagsbrun curve of rank 29
Not sure if this is surprising, but the discriminant factors as $-2^{19}\cdot 3^7\cdot 5^7\cdot 7^4\cdot 11^5\cdot 13^3\cdot 17^4\cdot 31^3\cdot 41^2\cdot 43^2\cdot 61^2\cdot 233\cdot 241^2\cdot 4139\...
- 844
3
votes
Is there a fast way to check if a matrix has any small eigenvalues?
YES, the pari/gp function called qfsign() does use rational numbers only!!!!! You may use it and not fear!
Got a reply from Bill Allombert himself, on a mailing list
Pari-gp has a version of what ...
- 25.7k
2
votes
Is there a fast way to check if a matrix has any small eigenvalues?
I am not currently allowed to comment, so I am writing this trivial observation as an answer instead.
A very slight variation of the method you are currently using is possible. The determinant is the ...
- 201
2
votes
What Turing degree would allow you to "compute" the axioms of ZFC in some countable model of ZFC?
Any PA degree is still sufficient. (Emil answered this in the comments, I'm just expanding on how to do it.)
To see this, let's remember the characterization of PA degrees:
${\bf d}$ is PA iff for ...
- 20.5k
2
votes
How to recover integer part from known fractional root part?
We have a number $f$, and we are looking for an integer $n$ such that $f^2 + 2f n = m$, where $m$ is an integer. This can be represented as two integer linear programs - program 1:
$$\max{2nf - m} \\ ...
- 3,319
1
vote
Accepted
Problem NP-completeness on a specific graph class
The answer is yes.
By taking complements, the maximum clique problem can be reduced to the maximum independent set problem (MIS) on graphs with degree $n/2-1$.
It is NP-hard to approximate MIS to ...
- 9,501
1
vote
Algorithm to construct basis for Kac-Moody algebra
I suppose that asking publicly somehow gave me the inspiration to figure it out after I had been stuck with it for a while. The answer is actually fairly straightforward. We can construct the Gram ...
- 111
1
vote
Accepted
Conjecture that relates matrix systems with some specific functions as solution sets
The affirmative answer and explicit solution to this question directly follows from my answer to the previous one by substituting there $u_i:=X^{Yi+Z}+1$ and $x:=X^Y$. Here I use capital letters to ...
- 34.3k
1
vote
Errors in Waksman's Solution to Cellular Automaton Firing Squad Problem?
Based on Gerhard Paseman's comment, I found the paper Correction, Optimization and Verification of Transition Rule Set for Waksman's Firing Squad Synchronization Algorithm by Umeo, Sogabe, and Nomura. ...
- 413
Only top scored, non community-wiki answers of a minimum length are eligible