The na.numerical-analysis tag has no wiki summary.
28
votes
5answers
3k views
Complexity of Finding the Eigendecomposition of a Matrix
My question is simple:
What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix?
Does eigendecomposition reduce to matrix ...
15
votes
2answers
1k views
How to compute powers of square matrices?
Suppose we are given a matrix $A \in \mathbb R^{N\times N}$, and let $m \in \mathbb N_0$. How fast can we compute the power $A^m$ of that matrix?
The next best thing in comparison to computing ...
8
votes
1answer
767 views
Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix
This is a specialized version of a previous question:
Complexity of Finding the Eigendecomposition of a Matrix .
For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the ...
8
votes
0answers
281 views
Efficiently approximating derivative of a well-behaved function
I need an algorithm for adaptive sampling a well-behaved function and computing its derivative in the sampling range with prescribed accuracy. The function has no more than one minimum in the sampling ...
7
votes
1answer
175 views
Numerically stable fast convolution algorithm?
Suppose you have two vectors of real numbers $\langle a_1, \dots, a_n \rangle, \langle b_1, \dots, b_n \rangle$, with $a_i, b_i \geq 0$, and wish to compute the convolution
$$
c_i = \sum_{j \leq i} ...
6
votes
2answers
279 views
Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model)
I know the Blum-Shub-Smale model. It is claimed to provide a theoretical framework for algorithms in real and complex algebra and analysis.
A very general question:
Most algorithms compromise of
...
6
votes
0answers
104 views
Numerical stability of Simplex method
The simplex algorithm is often treated either within real arithmetic, or in the discrete world with exact computations. However, it seems to be implemented most often with floating-point arithmetic.
...
6
votes
0answers
110 views
What's the state of the art for matrix nuclear/trace norm optimization
I am interested in simple matrix optimizations with nuclear/trace norm:
$\min_X \left(f(X) + \|X\|_*\right)$
where $\|X\|_*$ stands for the trace norm of the matrix $X$, and $f$ is a convex smooth ...
6
votes
0answers
101 views
What's new in sparse eigensystems solution
As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are ...
3
votes
1answer
58 views
Research papers regarding disinterval analysis
I'm trying to implement a disinterval analysis similiar to what is described in Clousot: Static Contract Checking with Abstract Interpretation (under section 5.2) - and I'm trying to find some papers ...
3
votes
0answers
68 views
Efficiently Detecting “edges” in the time frequency plane
Given a signal $y(t)\in\mathbb{R}$ I wish to detect edge patterns. $s(f,t)$ is a time-frequency decomposition of $y(t)$ in some window $(t-n,t+n)$ so that $f$ loosely corresponds to a local ...
2
votes
1answer
101 views
Finding mapping between two spatial representations of the same objects
I have two matrices $U$ and $V$. $U$ is $n \times n$ and $V$ is $n \times m$. (Both are empirical results of an experiment.) I would like to find a linear transformation $A$, $m \times n$, such that ...
2
votes
2answers
289 views
LU factorization of a 0-1 matrix
I have a rather naive question on LU factorization which probably should be easy to answer. Say I have a matrix with entries only from $\{0,1\}$. When can we expect to get an LU factorization of such ...
2
votes
1answer
131 views
Scaling procedures to address false 0's after multiplying probabilities
I need to translate a training algorithm that involves sums and multiplications of probabilities to actual code. For that I need some sort of scaling procedure that allows me to avoid underflows, that ...
1
vote
1answer
91 views
Adapted FEM mesh
Is there a technique where a square grid is used to as a mesh for time dependent partial differential equations (PDEs) but which the points are permuted in such a way as to minimize error?
e.g., ...
