# Questions tagged [numerical-algorithms]

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

113 questions
Filter by
Sorted by
Tagged with
28 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 ...
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 ...
44 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 ...
18 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 ...
24 views

372 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 ...
156 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 ...
49 views

614 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 ...
148 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: ...
43 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 ...
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 ...
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 ...
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 ...
989 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 ...
58 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 .
73 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$$ ...
50 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 ...
245 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 ...
133 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 ...
136 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 ...
732 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 ...
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) \... 1answer 35 views ### Theoretical precision needed to get n-bits of the evaluation of some sum Let P,Q two integral polynomials of height bounded by let say H>0 --- that is every coefficient of p or Q is bounded in absolute value by H --- and degree at most d. Let A a set of ... 1answer 117 views ### Finding a minimum of a noisy function I have a certain function that calculates numerically, for every x \in [0,10], a value y\geq 0. I want to find an approximate minimum point of that function. A possible solution is to calculate y... 0answers 37 views ### Not grasping Bayesian Monte Carlo I've read several sources of information that describe the process of Bayesian Monte Carlo Quadrature but am just not understanding the details enough to be able to implement it. For instance two ... 2answers 164 views ### Optimal generalized bisection method Suppose I'm looking for a some unknown number x in the interval [a,b] under the following assumptions: x is unique. Given any t \in [a,b] I can check, at some fixed computational cost, ... 1answer 39 views ### Accurate way to compute the sum of exponentials In my work, I had to essentially compute the following quantity. Given a sequence of positive floating point numbers \{a_i\}_{i=1}^n, such that$$6000 \leq a_i \leq 7000$$I needed to compute the ... 1answer 95 views ### Compute lebesgue measure of set of intervals Let S = \{ [x_1, y_1], [x_2, y_2], \dots, [x_n, y_n] \} be a set of not necessarily disjoint intervals on \mathbb{R}. Is there an efficient way to compute the lebesgue measure of the union \... 0answers 32 views ### numeric stability of map reduce operations I am building a small library for computing information retrieval metrics for classifiers (precision, recall, f1, accuracy, whatever). Typically each metric is built by calculating a single value for ... 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 ... 3answers 155 views ### Why aren't computables used for numerical calculations? In programming languages like Haskell you can use lazy evaluation to delay calculations. Why isn't a similar approach being used for numerical methods (I understand that there would be memory ... 1answer 48 views ### How to find a good saw function for PRNG? As part of an assignment I have to write a PRNG using a sin (or any other trigonometric function) and a saw function which I'm struggling a bit with. So how would you find a good saw function with ... 0answers 138 views ### predictor/corrector and gear integration for positive and negative time steps I have a predictor method that takes differential equations for 214 biological species and integrates them in time using positive time steps. Right now it is able to successfully integrate the ... 1answer 560 views ### Avoiding overflows while computing e^x by Taylor series I'm coding a program to calculate the value of e^x by using the Taylor expansion, that is:$$ e^x =\sum_{k=0}^\infty \frac{x^k}{k!}  ...
I want to approximate the output of a Monte Carlo simulation that takes a probability density function sampled at x-axis points $0,1,2,3,\ldots,n$ and outputs what tends to look like a dampened ...