# Tagged Questions

**2**

votes

**0**answers

64 views

### Lanczos algorithm with thick restart on a dynamic matrix

currently, I'm working on a way to compute the 2 biggest eigenvalues of a real, symmetric, huge and sparse matrix that changes a few entries from time to time. The problem should be solved using an ...

**2**

votes

**0**answers

122 views

### Algorithms to compute largest gap between smallest nonzero eigenvalues of sparse symmetric matrix

I am looking mainly for implementations but also for theoretical algorithms to compute gaps between smallest positive eigenvalues of symmetric, singular matrix or real numbers.
To be precise, I want ...

**1**

vote

**1**answer

203 views

### Does this algorithm terminate in all scenarios?

Let $x \in \mathbb{R}^p$ denote a $p$-dimensional data point (a vector). I have two sets $A = \{x_1, \dots, x_n\}$ and $B = \{x_{n+1}, \dots, x_{n+m}\}$, so $|A| = n$, and $|B| = m$. Given $k \in ...

**2**

votes

**0**answers

25 views

### In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?

I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...

**3**

votes

**1**answer

184 views

### Practical error-estimates for (adaptive) Newton-Cotes Quadrature

I am looking for practical error estimates for Newton-Cotes Quadrature rules.
Most books on numerical methods I have found mainly deal with theoretical error bounds/estimates for the respective ...

**6**

votes

**3**answers

637 views

### Square Root Algorithm

I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?

**3**

votes

**1**answer

143 views

### Using Fourier Transform to speed up calculation of forces following an inverse square law

Suppose I have $n$ electric point charges in, say, two dimensions. Is there any algorithm (and I have a hunch that it might be related to the Fourier transform) to compute the net forces that act on ...

**2**

votes

**1**answer

166 views

### Reducing the error of Algorithms by assigning variables formulas instead of values

Let me first give the intuition for my question: Suppose that you want to use a ruler to mark $n$ points in a line on a page, with 1 cm distance between neighbor points. There are two ways:
1- Mark ...

**16**

votes

**3**answers

841 views

### Easy functions ?

Let $f$ be an analytic function, and suppose that we want to compute
$f(x)$. The input consists of the digits of $x$ and the output of
a rational number approximating $f(x)$. A function $f$ is called ...

**-5**

votes

**2**answers

658 views

### why do we need algorithms, and why is non-convex optimization difficult? [closed]

A simple question, but (I'm quite sure) not a superficial one: is the basic distinction between algorithms and much of the rest of math that algorithms try to tackle problems for which we lack global ...

**0**

votes

**2**answers

364 views

### Is there a method to find (fit) a function with four (4) independent variables?

I have a system with 4 sensors (say $s_1..s_4$) which I want to combine into a single signal.
I have logged the 4 outputs as well as a "control" sensor ($s_c$) which has the desired ouput signal. ...

**8**

votes

**2**answers

382 views

### A competitive root finding game

Inspired by a question about bisection I wondered about the following: The are two players X and Y and a moderator Z who knows two (random,independent, uniformly chosen) hidden reals $x$ and $y$ from ...

**2**

votes

**3**answers

649 views

### Fast root finding for strictly decreasing function

What is a fast algorithm to find the root of a strictly decreasing function?
If the root is not exact I want to find a root such that the function value is positive to an error.

**0**

votes

**0**answers

408 views

### Decomposing max-convolution of sum of functions ?

Hello.
$R, F_1, F_2, F_3$ are random (not-convex, not-concave) 2D matrices of size 100x100.
$R$ is a linear combination of $F_1, F_2, F_3$.
Explicitly, $R = w_1 F_1 + w_2 F_2 + w_3 F_3$
where ...

**13**

votes

**2**answers

914 views

### Seeking proof for linear algebra constraint problem.

Given a symmetric real matrix with a zero diagonal $M$, I am trying to find a diagonal matrix $D$, such that the matrix $M + D$ is positive definite, and $(M+D)^{-1}$ has a diagonal consisting of all ...

**4**

votes

**2**answers

3k views

### Numerically most robust way to compute sum of products (standard deviation) in floating-point?

I stumbled across a paper by Welford (1962), where he proclaims a method that should compute the standard deviation numerically more robust than the naive algorithms ...

**0**

votes

**0**answers

583 views

### algorithm for solving systems of linear Diophantine inequalities

So, I posted on stack overflow looking for a reasonably fast algorithm to solve systems of linear Diophantine inequalities and was pointed to this article by Cheng-Zhi Gao and Yu-Lin Dong. The problem ...

**5**

votes

**6**answers

3k 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

**1**answer

342 views

### Nested root finding algorithm

I have a system of nonlinear algebraic equations which I'm wanting to solve numerically (for example with a Newton iteration based technique). I can formulate this either as the single system of size ...

**5**

votes

**4**answers

936 views

### Determining a recurrence relation

I would like to solve the general problem of determining a linear recurrence relation that fits a given integer sequence of length $n$, or stating that none exists (with fewer than $n/2-k$ ...

**7**

votes

**3**answers

1k views

### Are there ill-conditioned problems in infinite precision arithmetric?

It is hoped that in the future with the advent of quantum computing that fundamental operations on a computer will have arbitrarily high precision. Moreover, that even with such high precision, ...

**2**

votes

**0**answers

158 views

### Recovering a linear map from a non-linear approximation

The problem described here is algorithmic. We are given "black box access" to a map $f:R^d\to R^d$. By this we mean that one may query the value of $f(v)$ for an arbitrary $v\in R^d$.
We assume that ...

**5**

votes

**2**answers

508 views

### Runge-Kutta method with c<1

In trying to solve an ODE $y'=f(y,t)$ with a function f that is discontinuous at a subset (codim=1) of $\mathbb R^n$, I am looking for a Runge-Kutta ODE method whose stages do not evaluate $f(x,t)$ at ...

**7**

votes

**1**answer

641 views

### Best way to find a closest vector in a lattice

Let $v_1,\ldots,v_n$ be linearly independent vector in $\mathbb{R}^n$, and let $\Lambda=\oplus_i^n \mathbb{Z}v_i$. The question is, given a vector $w$ find the element $v$ of the lattice $\Lambda$ ...

**7**

votes

**4**answers

811 views

### Reasonable “Random” matrices to test numerical algorithms

Hello,
in numerical analysis, it is common to compare the behavior of different algorithms, and of different implementation of algorithms. This occurs not only on the theoretical level, but also on ...

**0**

votes

**0**answers

303 views

### Value of coefficient in estimation of computational complexity of polynomial division algorithm

Do you know value of coefficient $C$ at $C*n*log(n)$ in $O(n*log(n))$ estimation of complexity of polynomial division algorithm?
It would be great if you give me links to paper with information about ...

**6**

votes

**1**answer

556 views

### On Clenshaw's summation formula

When one has a finite sum of the form
$S=\sum_{k=0}^{n}{c_k F_k(x)}$
where $F_k(x)$ satisfies a two-term recurrence relation
$F_{k+1}(x)=\alpha_k F_k(x)+\beta_k F_{k-1}(x)$
the standard algorithm ...

**2**

votes

**1**answer

624 views

### Condition number for Ellipsoid method matrix

Hello,
When using the ellipsoid method (for solving a linear program for example), the volume of the ellipsoid at each iteration is proven to decrease, and do so by at least a factor of $e^{1/2n}$.
...

**30**

votes

**7**answers

2k views

### What is the time complexity of computing sin(x) to t bits of precision?

Short version of the question: Presumably, it's poly$(t)$. But what polynomial, and could you provide a reference?
Long version of the question:
I'm sort of surprised to be asking this, because ...

**1**

vote

**3**answers

330 views

### Numerical algorithms on mixed-precision computational models.

I want to learn more about numerical algorithms that use mixed-precision computational models (where instead of everything being 32/64 bit floating points, we can do lower precision calculations at ...

**23**

votes

**4**answers

2k views

### Can Gröbner bases be used to compute solutions to large, real-world problems?

In particular, suppose I have an affine algebraic variety over $\mathbb{R}^n$ described by generators of a radical ideal $I$ and I want to find (perhaps not all of the) points in the variety. Several ...

**9**

votes

**2**answers

2k views

### What is the constant of the Coppersmith-Winograd matrix multiplication algorithm

Or at least it's order of magnitude.
I've only ever heard it described as "huge", and a google search turned up nothing.
Also, given that the Strassen algorithm has a significantly greater constant ...