2
votes
1answer
41 views

Numerical evaluation of Hurwitz zeta function

Is there a way to evaluate numerically the Hurwitz zeta function $$\zeta(s,a) = \sum_{n=0}^\infty \frac{1}{(n+a)^{s}}$$ that is more efficient (i.e., quick and precise) than simply explicitly adding ...
1
vote
1answer
38 views

How to generate a point cloud with known symmetry?

So I would like to know if there are any published algorithms to generate point clouds with known symmetry groups, such as $D_{3h}$ or $O_h$ and stuff like that. I know lots and lots of point clouds ...
1
vote
1answer
35 views

Algorithm for retrieving all the permutations (randomized) for a vector sequence 1…N with only unique values

Here is the problem: I have a vector of $N$ elements long (containing only unique values from $1...N$). I am searching for an algorithm to obtain all the (randomized) combinations possible, where ...
0
votes
0answers
40 views

Fastest Algorithms for Determining the Nullity of a Matrix

How exactly does one go about determining the Nullity of a Matrix quicker than simply running Gaussian Elimination on the matrix itself? To be perfectly honest I can't think of a method that doesn't ...
0
votes
0answers
40 views

Global optimization

Assume that I want to find the global minimum of a non-linear, non-convex, multidimensional function subject to several restrictions. Could you recommend me any deterministic strategy which can ...
0
votes
1answer
54 views

Parity of number of factors up to a bound?

Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$. The question is to find a fast algorithm to find that ...
0
votes
0answers
19 views
1
vote
1answer
399 views

Solve non-linear equations of 3 variables using Newton-Raphson Method iterms of c,s and q.

The three non-linear equations are given by \begin{equation} c[(6.7 * 10^8) + (1.2 * 10^8)s+(1-q)(2.6*10^8)]-0.00114532=0 \end{equation} \begin{equation} s[2.001 *c + 835(1-q)]-2.001*c =0 ...
7
votes
1answer
187 views

Fast algorithm for approximating Eigenvalue distribution of large sparse matrix

I am interested in the eigenvalue distribution of a huge $2^{16}$x$2^{16}$ Hermitian sparse matrix with spectrum contained in $[-1,1]$. That is I don't need to know all eigenvalues exactly, but rather ...
3
votes
1answer
366 views

What initial guess is used for finding n-th root using Newton-Raphson method?

I would like to know what is an optimal initial guess for use with Newton-Raphson method when finding n-th root. I develop some program which uses GMP C++ library. GMP manual says: The initial ...
1
vote
1answer
54 views

Laguerre's method and zero division

I'm trying to understand Laguerre's method for root finding and I have hit one road block. Suppose I have a polynomial $p(x) = x^4 + 1$ and an initial guess $x_0 = 0$. This results in division by ...
1
vote
3answers
115 views

How to choose the starting point in Newton's method?

How to choose the starting point in Newton's method ? If $p(x)=x^3-11x^2+32x-22$ We only learnt that the algorithm $x_{n+1}:=x_n-\frac{f(x_n)}{f'(x_n)}$ converges only in some ...
0
votes
1answer
53 views

Checking convergence of an iteration

How to check if an algorithm converges in an interval, for example $x_{k+1}:=\frac{1}{11}(1-\cos(x_k))$ does it converge for any startpoint $x_0\in (-\pi/2,\pi/2)\setminus\{0\}$ ? (as hint: ...
0
votes
0answers
24 views

Iteratively solve linear equations with rank-1 updates on LHS and RHS

What is the best way to iteratively solve updating equations of the form $$ Ax=b $$ $$ (A+c_1v_1^\intercal)x_1=b+ \alpha_1 d_1 $$ $$ (A+c_1v_1^\intercal+c_2v_2^\intercal)x_2=b+\alpha_1d_1+\alpha_2d_2 ...
1
vote
0answers
52 views

Approximating the smallest positive root of a function

Suppose we have a smooth function $f:\mathbb{R}\rightarrow\mathbb{R}$. Let $S$ denote the set of all positive roots of $f$ and let $x^*$ denote the minimum of $S$ (assuming such a thing exists). What ...
0
votes
1answer
41 views

How to extract all the points from a noisy surface?

I have points representing a bridge like in this picture: My goal is to get all the points that are in the red box. These points all share a common surface that is not necessarily planar. The ...
2
votes
0answers
51 views

Expected error due to the tablemakers' dilemma

[note: to me, this does not seem like a question for m.se, but on mathoverflow it has been retroactively closed, with very little indication of why or what might be corrected... and waiting for ...
8
votes
1answer
224 views

Stochastic gradient descent for convex optimization

What happens if a convex objective is optimized by stochastic gradient descent? Is a global solution achieved?
5
votes
3answers
251 views

FFT with powers of 3

Classic Fast Fourier Transfrom (FFT) works fine, when $n$ is power of 2. How to generalize FFT procedure when $n$ is power of 3? Is it possible to easily modify the algorithm and preserve its ...
0
votes
0answers
39 views

constrained minimization in N dimensions

I am looking to create an algorithm to minimize an N dimensional problem. I am unsure how to write it in its generic form, so I will show it in 1, 2 and 3 dimensions Minimize $ \sum_{i} x_i\left [ ...
0
votes
3answers
308 views

Subtracting two dates

I'm developing a software and I need to subtract two dates and then get a date again. I've been trying to solve this problem for a while and I have found some additional problems. One of these ...
2
votes
3answers
142 views

How bad, really, is the bisection method?

We know that the bisection method for root finding is slow (linear convergence), but has the advantage of always working for a continuous function, if we start with a interval which brackets the root. ...
1
vote
3answers
68 views

Newton's method for square root

Solving $x^2-a=0$ with Newton's method, you can derive the sequence $x_{n+1}=(x_n + a/x_n)/2$ by taking the first order approximation of the polynomial equation, and then use that as the update. I can ...
3
votes
2answers
56 views

Non-iterative solution for $(a + nb)\mod c < d$

With the given parameters $a$, $b$, $c$, and $d$ I'm looking for a solution of the formula $(a + nb)\mod c < d$. The smallest positive $n$ is the value I want to determine. I can easily solve ...
0
votes
1answer
148 views

Calculate the interpolation polynom with Neville scheme

i have the following: $P \in \Pi_3$ is the interpolation polynom with $P(x_i)=f_i$, for $$x_i \quad -1 \quad 0 \quad 1 \quad 3$$ $$f_i \quad 5 \quad -6 \quad -9 \quad 33$$ (table) I want to ...
1
vote
2answers
252 views

Minimum number of iterations in Newton's method to find a square root

I am writing an algorithm that evaluates the square root of a positive real number $y$. To do this I am using the Newton-Raphton method to approximate the roots to $f(x)=x^2-y$. The $n^{th}$ iteration ...
4
votes
2answers
188 views

Using Newton's method calculate $ \frac{1}{\sqrt{a}} $ without division

Suggest algorithm for the numerical calculation $ \frac{1}{\sqrt{a}} \ a > 0 $ without division, use Newton's method. My idea is: $$ \frac{1}{\sqrt{a}} = (\sqrt{a})^{-1} = a^{-\frac{1}{2}}$$ $$ x ...
1
vote
2answers
535 views

Newton's method for polynomial interpolation

I've seen that in Newton's method for interpolating polynomials, the coefficients can be found algorithmically using (in Python-ish): ...
1
vote
0answers
56 views

Algorithm for finding power

I has been searching for a high precision library in PHP to do calculations like $$232323232323^{121212.2232323232}$$ etc (ie, with very large numbers, including decimals), but failed to get any. ...
0
votes
1answer
58 views

Need Help! Recognizing types of errors: Truncation and Roundoff

I am a little unclear on the difference between the two. What exactly are they? As simplified as possible :) How can i recognize them and identify parts of formulas or algorithms that would give ...
2
votes
1answer
515 views

Find an efficient algorithm to calculate $\sin(x) $

Suggest an efficient algorithm to determine the value of the function $ \sin(x) $ for $ x \in [-4\pi, 4\pi] $. You can use only Taylor series and $ +, -, *, /$. I know, that $$ \sin(x) = ...
1
vote
2answers
41 views

Solving system of linear eqaution in special cases

I have to solve for $Ax=B$. Here the diagonal elements of $A$ are $-1$ and all other elements are $1$. $A$ is $n \times n$ matrix . In this special case can we solve for $x$ quickly? EDIT: quick is ...
2
votes
1answer
147 views

how to show the convergence of an algorithm

I have two unknown variables x and y which are non linear equations to be solved. \begin{eqnarray} y=\frac {|\sin(2x+\theta)|}{\sin x\sqrt{A+2B\cos(2x+\theta)}} \nonumber \\ x=\arccos\bigg( ...
2
votes
3answers
115 views

If I know that a polynomial (of order $k \gt 2$) has at most $1$ positive real root - can I find that easily?

[update 2] Urgghh - the time-consumption really stems only from the construction of the h-order polynomial. The time for finding the roots (only 10 to 20 times Newton-iteration because of my nice ...
0
votes
1answer
98 views

Bounding a bicubic polynomial

My actual situation is working with bicubic polynomials, (that is, polynomials of the form $\sum_{i=0}^3 \sum_{j=0}^3 a_{i,j} x^iy^j$) defined on the unit square $[0,1]^2$ (actually these are ...
10
votes
1answer
232 views

Is there an efficient method for the calculation of $e^{1/e}$?

(I wonder whether this is appropriate for the Math StackExchange or whether it'd be better on Stack Overflow as it deals with computing, but I'm asking about mathematical details, not about ...
1
vote
1answer
183 views

How do deal with a giant sparse matrices?

Someone point me in the right direction. I'm looking to do some heavy-duty manipulation of some really large and often very sparse matrices. Naturally, this problem overlaps programming heavily (I ...
1
vote
0answers
97 views

Algorithm of projection

Suppose $S$ is a compact surface in $\mathbb{R}^{3}$ defined by a sufficiently smooth level set function $f$, that is, $S=\{s: f(s)=0\}.$ I am studying an algorithm that projects a point $x_{0}$on ...
0
votes
1answer
173 views

optimization of a non-differentiable, component-wise step function

I would like to estimate the (local) minimum of a function $c:R^N \mapsto R^+$ where: $c$ is only differentiable almost everywhere, there exists a component $j$, such that $\frac{\partial ...
2
votes
1answer
106 views

Algorithm analysis

Consider a recursive Mergesort implementation that calls Insertion Sort on sublists smaller than some threshold. If there are n calls to Mergesort, how many calls will there be to Insertion Sort? ...
0
votes
0answers
148 views

Bluestein Algorithm for Fast Fourier Transform

Can anyone demonstrate the full algorithm of Fast Fourier Transform? Because from Wikipeida and other internet sources, I saw that there are different ways of padding. So can anyone tell me when the ...
4
votes
0answers
170 views

Test for equivalence of algebraic expressions

We are looking for the most efficient (most recent, or best) techniques to check if two algebraic expressions (elementary, Calculus-type functions) are equivalent (or if an expression is equivalent to ...
1
vote
0answers
147 views

Gradient Descent in a 3D parameter space

I'm trying to computationally implement a gradient descent algorithm in 3D to find the maxima of a function. I want to use a recursion scheme like $$\textbf{x}_{k+1} = \textbf{x}_k + \alpha \nabla ...
2
votes
0answers
45 views

Finding $k$ unknowns given the sum of their first $k$ powers

Motivation: The motivation for this question came from a Computer Science problem of finding duplicates in a list in constant time and constant space. If the list of numbers was $i_1, i_2, \ldots, ...
7
votes
0answers
184 views

What’s the best way to cut an apple?

Take the apple in one hand, and the knife in the other. In the first cut, the apple is divided in two pieces: a small one that drops into the plate and a big one that is still hold with the hand. This ...
1
vote
0answers
32 views

A journal for the article related to methods for solving Cauchy equations

I'm a postgraduate student in physics, but I have achieved interesting results in Cauchy equation. I found a reason why Adams method for solving differential equations gives rise to divergent ...
2
votes
0answers
122 views

monotonic smoothing fit to be implemented (in python or other language)

In a post that already exists, implementation-of-monotone-cubic-interpolation, there is a good method for fitting data which necessarily includes all of the given points. But, what if I need to ...
3
votes
2answers
75 views

Aproximating rational with fraction with “smallest numerator and denumerator possible”

For example $0.795=\frac{159}{200}$. But is there a way to find fraction with smaller numerator and denumerator that will represent number $0.795xyz...$ i.e. it will approximate our given number? I ...
0
votes
1answer
89 views

Better than Runge-Kutta-Fehlberg 4(5) at high order?

I wonder what are currently the best numerical solvers of ODE for high-accuracy computations. I need an efficient and accurate method to solve ODE that are not pathological (all is smooth) using ...
1
vote
2answers
44 views

How to check if a number has reached given precision?

So right now I'm working on an algorithm which has to know when to terminate its calculations - namely, it should do it when the number he's acquired in the last step is at least as precise as the ...