Questions tagged [numerical-algorithms]

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

Filter by
Sorted by
Tagged with
0
votes
6answers
127 views

What algorithm do computers use to compute the square root of a number?

What algorithm do computers use to compute the square root of a number ? EDIT It seems there is a similar question here: Finding square root without division and initial guess But I like the answers ...
0
votes
0answers
34 views

How to express a parabola as a Bezier curve

I need to create a parabolic shape with a given starting point, maximum point, and end point. I thought the most efficient way to do this is to use a bezier curve. However there is no major ...
1
vote
1answer
61 views

Adaptive step size constrained to a limited number of iterations

I'm solving a differential equation on the form $\ddot x = f( \dot x, x)$ on a microchip within a limited (real world) time frame, hence I want to use an adaptive step size to get as good of a result ...
3
votes
2answers
85 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: ...
1
vote
1answer
53 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
33 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
42 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
39 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
114 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 ...
2
votes
1answer
44 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 ...
1
vote
1answer
23 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 ...
5
votes
5answers
298 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 ...
0
votes
1answer
95 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 ...
0
votes
1answer
29 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 ...
1
vote
1answer
58 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
210 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
22 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 ...
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-...
0
votes
1answer
62 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
383 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 ...
0
votes
2answers
87 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 ...
2
votes
1answer
161 views

numerically stable log1pexp calculation

What are good approximations for computing log1pexp for single precision and double precision floating point numbers? Note: ...
2
votes
2answers
49 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
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 ...
2
votes
1answer
29 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....
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
36 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
571 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
198 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 ...
1
vote
1answer
55 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}$...
3
votes
1answer
94 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 ...
3
votes
0answers
42 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
667 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
1answer
169 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: ...
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 ...
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 ...
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
67 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 ...
0
votes
0answers
66 views

Naviers Stokes equation and machine learning

I am looking for a reference explaining how to solve Navier-Stokes numerically using Machine learning algorithms . Thank you in advance for your help .
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$$ ...
1
vote
1answer
52 views

Efficiently compute parallel matrix-vector product for block vectors?

I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I now want to compute the matrix-vector product $$w = (E\otimes I_N)v$$ in parallel, where $\otimes$ is the ...
0
votes
2answers
627 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 ...
6
votes
1answer
154 views

What is the role of Numerical Gradient Computation in Backpropagation algorithm?

I was listening CS231n (2017) lectures and noted that there is a lot of attention to Numerical Gradient Computation (NGC). It starts @5:53 in this video and appears a few times later. Also, looking ...
0
votes
0answers
150 views

Algorithm to find extrema of a function?

What are some simple algorithms that find the maximum of a function in a certain domain? The function $f$ is guaranteed to have 1 maximum and no other turning points between $a$ and $b$, how can I ...
0
votes
1answer
881 views

How to prove that matrix inversion is at least as hard as matrix multiplication?

Suppose we are given a matrix $A$ over real numbers and we want to computer the inverse of matrix $A$. There are various algorithms to do so and it also turn out that we can use matrix multiplication ...
2
votes
1answer
87 views

Calculating this sum in $O(n)$ time

Assume that $\forall 1 \leq i \leq n : a>0, c_i > 0 $ where $n \in \mathbb{N}$. I need to show that it is possible to compute this sum in $O(n)$ time: $$I = \sum_{(\epsilon_1,...,\epsilon_n) \...