Questions tagged [numerical-algorithms]

Questions related to algorithms that use numerical approximations for the problems of mathematical analysis.

Filter by
Sorted by
Tagged with
3
votes
2answers
54 views

How can I compute logarithm when comparison is undecidable?

In Haskell, I have the following datatypes that encodes arbitrary real numbers and arbitrary complex numbers, respectively: ...
8
votes
2answers
754 views

Is “ternary search” an appropriate term for the algorithm that optimizes a unimodal function on a real interval?

Suppose that I want to optimize a unimodal function defined on some real interval. I can use the well-known algorithm as described in Wikipedia under the name of ternary search. In case of the ...
1
vote
1answer
47 views

Cancellation in C++

I am trying to figure out what the problem with the following expression in C++ is: y=std::log(std::cosh(x)); My first intention was that there might occure a ...
0
votes
1answer
29 views

$f(x) = \sqrt{x^{2}+1}-1$ (Loss of Significance)

Let us say that I want to compute $f(x) = \sqrt{x^{2}+1}-1$ for small values of $x$ in a Marc-32 architecture. I can avoid loss of significance by rewriting the function $$f(x)=\left(\sqrt{x^{2}+1}-1\...
0
votes
2answers
37 views

convergence rate of newton's method

So, I'm currently studying Newton method used for finding the 0's of a function, however my professor has only announced that the speed of this algorithm can be more than quadratic, however I'm ...
1
vote
2answers
35 views

Validity of Algorithm for Testing Two Floating Point Numbers

This question is related to the epsilon- (or delta- if you prefer) test for floating point equality. But my question is not how to do it. Instead I have a related algorithm for testing equality, and I ...
0
votes
0answers
20 views

Books on scientific computing, efficent NN inference, and matrix multipication

I'm trying to learn more about how inference, matrix multiplication, and scientific computing (primarily with tensors/matrices). I'm not sure what the classics here are or what good sources are. I'm ...
1
vote
1answer
38 views

foresightful acceleration and decelerations

I am programming a CNC machine (using matlab). In order to generate a surface with a "high" shape accuracy (order of $1\mu m$) and "small" micro roughness (order of few nm) I need ...
1
vote
3answers
103 views

Algorithm to compute power function on interval [0, 1]

I am looking for an efficient algorithm to compute $$f(x) = x^a, x\in[0, 1] \land a\,\text{constant}$$ If it helps, $a$ is either $2.2$, or $1/2.2$. Knowing valid values for $x$ and $a$ could make it ...
5
votes
5answers
274 views

fast and stable x * tanh(log1pexp(x)) computation

$$f(x) = x \tanh(\log(1 + e^x))$$ The function (mish activation) can be easily implemented using a stable log1pexp without any significant loss of precision. Unfortunately, this is computationally ...
2
votes
1answer
137 views

numerically stable log1pexp calculation

What are good approximations for computing log1pexp for single precision and double precision floating point numbers? Note: ...
2
votes
1answer
41 views

O(m+n) Algorithm for Linear Interpolation

Problem Given data consisting of $n$ coordinates $\left((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\right)$ sorted by their $x$-values, and $m$ sorted query points $(q_1, q_2, \ldots, q_m)$, find the ...
0
votes
1answer
48 views

Converting a number to 16-bit Floating Point Format

I want to convert the number -29.375 to IEEE 745 16-bit floating point format. Here is my solution: The format of the floating point number is: 1 sign bit unbiased exponent in 4 bits plus a ...
1
vote
1answer
22 views

Complexity of numerical derivation for general nonlinear functions

In classical optimization literature numerical derivation of functions is often mentioned to be a computationally expensive step. For example Quasi-Newton methods are presented as a method to avoid ...
0
votes
1answer
23 views

Algorithm to calculate Polylogarithm

In my code i want to solve the Fermi-Dirac-Integral numerically. This can be achieved with a Polylogarithm. Actually I'm coding in C#, so my function to calculate ...
6
votes
2answers
676 views

generating pi using Machin like formula

Back in 2002, using this arctan formula for pi discoverd by Stoemer: $$ \pi = 176 \arctan(1/57) + 28 \arctan(1/239) - 48 \arctan(1/682) \\ + 96 \arctan(1/12943)$$ and I assume using this ...
1
vote
1answer
31 views

How were weights chosen in Runge-Kutta (4) method?

Consider an ODE $\dot y = f(t, y)$. We will approximate the value of $y$ using the 4th-Order Runge-Kutta method. Let $\Delta$ be the step size, then in step $i+1$ we have $~y_{i+1} = y_i + deriv\cdot\...
3
votes
1answer
2k views

Understanding the Broyden–Fletcher–Goldfarb–Shanno Algorithm to Select Weights for Neural Nets

I am trying to train and implement a Neural Network. I was reading a few articles, learning about their principles and the math that goes behind them. However, while I was trying to understand the ...
2
votes
2answers
47 views

Search for numerical solutions of underdetermined systems of quadratic equations

I'm looking for an algorithm that can quickly generate an approximate real number solutions of an underdetermined quadratic system. My task is to explore its algebraic variety. I'm interested in a ...
3
votes
1answer
115 views

Robust two lines/segments intersection point in 2D

Given two line segments the problem is to find an intersection point of corresponding lines (assuming that they are not parallel or coincide). There is a Wikipedia article which gives us exact ...
1
vote
0answers
20 views

Algorithm to position samples minimizing error

We have a 1D function f(x). We would like to approximate this function with a polyline of n points. How can we find the ...
3
votes
1answer
89 views

Could a Van Emde Boas tree be used for storing matrices?

I'm aware that typical techniques to store matrices in sparse form are compressed formats or maps where the key is the pair of indices and value the value of the entry in a matrix. I was wondering if ...
0
votes
0answers
7 views

Efficiently populate a look-up table for a function over a range of arguments

I am minimizing a scalar function $f$ which takes a $n$-dimensional vector input and outputs a scalar value. I have code that given an input $x$ will compute the output of $f(x)$ (a scalar), its ...
1
vote
0answers
18 views

Are there practical usage of determinants in numerical simulation?

I know the historical importance of the link between linear systems and determinants. I also know that determinants have a beautiful connection with non-singular matrices, i.e., if a matrix is non-...
4
votes
2answers
663 views

Numerical stability of linear interpolation

Is one of these two functions more numerically stable than the other? ...
0
votes
2answers
85 views

How to find i-th root of n whose remainder is the smallest?

Given a number n, what is the most assymptotically fast algorithm to express it in terms of base^exponent + rem such that rem is the smallest possible and base is limited from 2 to some relatively ...
6
votes
1answer
4k views

Efficient way to calculate the maximum curvature of a cubic spline

I've got a 2D cubic spline (Bézier) and I have the polygon-line that's a discretization of that spline. Is there an efficient and simple to implement a way to calculate the maximum curvature of the ...
0
votes
1answer
61 views

Computing an Expression

I am writing code to evaluate the following expression: $$ \frac{(a+b+c)!}{a! b! c!} $$ where $a$, $b$ and $c$ are on the range of $10$ to $500$. The result is going to be a floating point number. ...
5
votes
4answers
334 views

Is order of matrix multiplication affecting numerical accuracy of the result?

I have to multiply three matrices of floats: A (100x8000), B (8000x27) and C (27x1). Is ...
1
vote
1answer
50 views

How can I minimize floating point error when multiplying normal distribution PDFs?

If you multiply two normal distribution PDFs with means $\mu_1$ and $\mu_2$ and variances $v_1$ and $v_2$, then according to this page, the new mean is $$\mu = \frac{\mu_1 v_2 + \mu_2 v_1}{v_1 + v_2}$...
10
votes
3answers
5k views

Fastest way to solve a system of linear equations

I have to solve a system of up to 10000 equations with 10000 unknowns as fast as possible (preferably within a few seconds). I know that Gaussian elimination is too slow for that, so what algorithm is ...
3
votes
0answers
50 views

Efficient algorithm for numerical estimation of 3D rotation matrix

I am writing a computer vision related program and stuck on a problem. I have a system of quadratic equations where M is a constant 3x3 matrix, is the 3x3 identity matrix, and we are solving for the ...
6
votes
1answer
4k views

Multi-point evaluations of a polynomial mod p

Given a polynomial of degree $n$ modulo a prime number $p$, I want to evaluate that polynomial at multiple values of the variable $x$, what is the best way to do this? I tried using Berlekamp's ...
2
votes
1answer
27 views

When an algorithm says Summation this, and Integral that, what does it mean in coding terms?

I'm a student at a college with only two units of mathematics and I don't know if I'm asking in the right place so please bear with me. I'm currently reading GPU Gems by nvidia and I have a question....
2
votes
1answer
135 views

Check if a given polynomial is primitive

I try to estimate error detection capabilities of arbitrary CRC polynomials. One important criteria is if a given polynomial is primitive. So I need an algorithm to check that. My goal is to write a C ...
3
votes
1answer
29 views

Rigorous error bounds for eigenvalue solvers

I computed the first four eigenvalues of a quite large ($2^{24}\times 2^{24}$) but very sparse matrix. I used pythons in-build function sparse.linalg.eigsh to compute them. I need a validation that ...
0
votes
0answers
35 views

Application of iterative algorithm $(\theta_n,w_n)$ converging to $\{(\theta,\theta):\theta \in \Bbb R\}$

I have a iterative algorithm $(\theta_n,w_n)$ which I am showing converges to $\{(\theta,\theta):\theta \in \Bbb R\}$. The iterative algorithm is of the form : $\theta_{n+1} = \theta_n + a(n)[h(\...
0
votes
2answers
454 views

How to test for overflow when multiplying floats

I am trying to implement a 3-term recurrence relation: $$ p_{n+1} = ap_n + bp_{n-1} $$ This can be implemented as ...
5
votes
0answers
175 views

What is the state of the algorithmic art for floating point arithmetic on complex numbers?

Most modern compilers and processors implement the IEEE 754 binary formats for floating point numbers. IEEE 754 guarantees that the addition, subtraction, multiplication, division, and square root ...
3
votes
0answers
40 views

How to compute the loss and backprop of word2vec skip-gram using hierarchical softmax?

So we are calculating the loss $$J(\theta) = -\frac{1}{T}\sum_{t=1}^T\sum_{-m \leq j \leq m} \log P(w_{t+j}|w_t;\theta)$$ and to do this we need to calculate $$P(o|c) = \frac{\exp(u_o^Tv_c)}{\sum \...
5
votes
1answer
629 views

Algorithm for using power series to numerically solve a partial differential equation given a boundary condition?

Motivation: Following this discussion about using asymptotic expansions (i.e. polynomial power series) for numerically solving partial differential and algebraic equations (PDAE), I couldn't find any ...
3
votes
3answers
2k views

Calculating decimal digits of pi, using something similar to a Bailey–Borwein–Plouffe formula

I have tried to Use the Bailey–Borwein–Plouffe formula to calculate pi to 3 digits as a test trial, and recieved the digit 4, which is technically correct, as 4 is the 3rd digit of pi in base 16. I ...
3
votes
1answer
159 views

Understanding truncation and rounding error in IEEE floating point system?

I'm trying to understand the theory behind finding the optimal $h$ value for differentiation in this definition: $$ \frac{f(x+h) - f(x)}{h}$$ as $h$ tends to 0. Here is my understanding: ...
0
votes
2answers
504 views

UInt128 - Compute the product of two UInt128's that are each represented by two UInt64's?

I have a struct like this: struct UInt128 { UInt64 s1; UInt64 s2; } In this struct, s1 represents the highest 64-bits ...
5
votes
1answer
2k views

Why is adding log probabilities considered “numerically stable”?

Every once in a while, I come across the term numerical stability, which I don't really understand. In particular, I have seen a description of the practice of "adding logs rather than multiplying ...
4
votes
0answers
44 views

Symbolic Math Systems As Speculative Optimization For Numerical Software?

Has there been published work on hiding symbolic math within numeric software, partitioning parallel processes between speculative symbolic optimization search and numeric evaluations? Real world ...
0
votes
1answer
33 views

Computation time of a Binom matlab (or C) routine

I am trying to write a Matlab (or C) routine for the exact probability F of observing K or more successes when a success probability P is expected ($\sum_{k=i}^n \binom{n}{k}p^k(1-p)^{n-k}$). I am ...
4
votes
2answers
66 views

Union of fixed and floating point types

Say I have two real number types. They may be floating or fixed point. How can I construct a new type whose values are at least the union of the two with the minimal number of bits? There are 3 cases ...
0
votes
3answers
1k views

How approximate sine using Taylor series

I need to approximate the sine function without internal libraries. I used Taylor series in 0 to solve this, but my program works for some values, but for others awful results. The program gets x ...
1
vote
1answer
74 views

Efficiently compute parallel matrix-vector product for block vectors with FFTs?

Assume I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I learned in this question/answer that for computing the matrix-vector product $$w = (E\otimes I_N)v$$ ...