The tag has no wiki summary.

learn more… | top users | synonyms (1)

25
votes
1answer
551 views

Computational complexity of pi

Let $L = \{ n : \text{the }n^{th}\text{ binary digit of }\pi\text{ is }1 \}$ (where $n$ is thought of as encoded in binary). Then what can we say about the computational complexity of $L$? It's ...
0
votes
1answer
58 views

Multiple independent random number streams

Having multiple streams of pseudo-random numbers known to be independent and with a uniform distribution I want to do Monte Carlo simulations in parallel. In other words, one thread will have a ...
12
votes
5answers
333 views

Motivation for volume estimation

What are some concrete and compelling applications for estimating the volume of convex polyhedra of the sort considered in the more recent papers on random walk methods? These papers on volume ...
9
votes
1answer
298 views

Integer roots of a polynomial

What algorithm can we use to find all integer roots of a polynomial $f(x)$ with integer coefficients? I observe that Sage can find the roots within a few seconds even when all coefficients of $f(x)$ ...
3
votes
2answers
1k views

Universal Approximation Theorem — Neural Networks

I posted this earlier on MSE, but it was suggested that here may be a better place to ask. Universal approximation theorem states that "the standard multilayer feed-forward network with a single ...
1
vote
1answer
102 views

Delimiting the roots of a polynomial

Given a polynomial of degree $n$, namely, $y=a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0$, with $a_i\in \mathbb{R}$, I would to know if it is possible to compute a rational number $K$ such that the ...
7
votes
0answers
143 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. ...
7
votes
1answer
281 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} ...
3
votes
1answer
65 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
76 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 ...
8
votes
0answers
318 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 ...
16
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 ...
2
votes
1answer
104 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 ...
6
votes
0answers
116 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 ...
1
vote
1answer
142 views

Most optimal parallel method for calculating the integral of a 2D function

I posted already this question to SO but got no answer so I try it now here: In some crunching number program, I have a function which can be just 1 or 0 in three dimensions. I do not know in advance ...
1
vote
0answers
105 views

Optimal parallel algorithm for finding roots of a function [closed]

In some problem I need to find the zeroes (multiple real solutions) of some functions in 1D and 2D. I wonder which is the best parallel algorithm for this, which can provide the highest accuracy and ...
1
vote
0answers
98 views

High Dimensional Volume (HDV) estimator for Entropy estimation

I am writing a program using high-dimensional volume (HDV) estimator to estimate entropy and mutual information for variable selection. Let $ D = (x^i_1, x^i_2, ..., x^i_M)$, N is the number of data ...
7
votes
0answers
109 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 ...
2
votes
2answers
323 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 ...
6
votes
2answers
321 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 ...
1
vote
1answer
94 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., ...
2
votes
1answer
137 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 ...
9
votes
1answer
919 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 ...
34
votes
5answers
5k 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 ...
21
votes
6answers
1k views

How are real numbers specified in computation?

This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real ...