1
vote
0answers
61 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
0answers
116 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
1answer
200 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
0answers
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
1answer
183 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
3answers
630 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
1answer
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
1answer
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
3answers
840 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
2answers
654 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
2answers
361 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
2answers
380 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
3answers
635 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
0answers
405 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
2answers
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
2answers
2k 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
0answers
578 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
6answers
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
1answer
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
4answers
935 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
3answers
986 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
0answers
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
2answers
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
1answer
640 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
4answers
808 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
0answers
301 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
1answer
549 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
1answer
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
7answers
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
3answers
328 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
4answers
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
2answers
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 ...