Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [numerical-algorithms]

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

4
votes
0answers
50 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 ...
0
votes
1answer
20 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}$...
1
vote
1answer
34 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
26 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
494 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 ...
0
votes
0answers
11 views

Numerical integration on a part of the domain using quadratures

I have relatively simple question and I did not find the answer yet. Suppose I want to numerically integrate a function. Using simplest scheme with equal weights, it is easy: $$ \int_{0}^1f(x)dx=\...
0
votes
0answers
10 views

Why does economising the power series give me more error?

Suppose I want to economise $\sin x$ with the following taylor series: $$P_{2n-1}(x) = \sum^n_{i=1}(-1)^{i-1}\frac{x^{2i-1}}{(2i-1)!}$$ for the interval $[-1, 1]$ for $P_5(x)$. For $P_5(x)$, I have ...
3
votes
1answer
47 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
39 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 ...
4
votes
1answer
351 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
29 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
46 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
121 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
42 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
67 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
42 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
57 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
83 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
57 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
316 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
80 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) \...
1
vote
1answer
32 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 $...
4
votes
1answer
68 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$...
2
votes
0answers
35 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 ...
1
vote
2answers
121 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, ...
1
vote
1answer
35 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 ...
1
vote
1answer
74 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 $\...
2
votes
0answers
29 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 ...
7
votes
3answers
2k 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 ...
5
votes
3answers
150 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 ...
0
votes
1answer
41 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 ...
1
vote
0answers
94 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 ...
3
votes
1answer
257 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!} $$ ...
3
votes
1answer
59 views

ML to approximate a dampened harmonic oscillator from a related curve

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 ...
1
vote
2answers
61 views

Real-valued genetic algorithm offspring out-of-bounds

I have a fairly simple real-valued genetic algorithm that seems to work fairly well, however it currently has some issues that I'm hoping to get some help with. If we consider a 1-dimensional problem, ...
-1
votes
1answer
19 views

How do I classify the improvement in performance when Hankel functions are replaced with log functions in MatLab?

I am working on a algorithm for acoustic scattering in two dimensions using MatLab, and one of the advantages of this algorithm is that Hankel functions can be replaced with log functions. For ...
3
votes
1answer
160 views

Cost of solving a matrix equation using the FFT

I am trying to calculate $$V = (H^TH+I)^{-1} U$$ where $H\in\mathbb{R}^{m\times m}$ is a circulant convolution matrix corresponding to a convolution kernel $h$, and $U\in\mathbb{R}^{m\times n}$. ...
6
votes
1answer
364 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 ...
3
votes
1answer
110 views

Generating Pairs of Random Numbers

Please consider the following probability density function of two variables. \begin{eqnarray*} f(x_1,x_2) &=& \begin{cases} 2(x_1+x_2) & \text{for} \,\, 0 \le x_1 \le x_2 \le 1\\ 0 ...
0
votes
1answer
169 views

The stability of log(1+x)

I am trying to understand why the formula $$ \frac{\log(1+x)}{(1+x)-1} \times x,$$ which simply reduces down to $\log(1+x)$, is considered as more stable to compute than $\log(1+x)$. In my head it ...
0
votes
1answer
527 views

Running time of sparse matrix multiplication

Given a sparse matrix $M \in \mathbb{R}^{n \times m}$ with $n \ll m$ and $\mathsf{nnz}$ being the number of non-zero-components. What is the running time of computing $M M^T$?
3
votes
1answer
35 views

Algorithmic Complexity of Statistical Estimators

This might be very basic but I am interested in evaluating the algorithmic complexity of an estimator of the form: $$\hat{\theta} = \text{argmin}_{\theta} \;\; Q_n (\theta)$$ where $Q_n(\theta)$ ...
4
votes
1answer
209 views

MDS minimization with gradient descent

I have the following multiple dimensional scaling (MDS) minimization problem in vectors $v_1, v_2, \dots, v_n \in \mathbb R^2$ $$\min_{v_1, v_2, \dots, v_n} \sum_{i,j} \left( \|v_i - v_j\| - d_{i,j} \...
15
votes
4answers
1k views

Inequality caused by float inaccuracy

At least in Java, if I write this code: float a = 1000.0F; float b = 0.00004F; float c = a + b + b; float d = b + b + a; boolean e = c == d; the value of $e$ ...
1
vote
0answers
70 views

Parallel algorithm for Chinese remainder theorem

What is the most efficient (in terms of running time) algorithm that solves the Chinese remainder theorem (CRT) on a set of integer residues. That is, given a set of moduli $\{m_i\}_{i=1}^{r}$ and set ...
2
votes
2answers
590 views

Floating Point Systems - Rounding Error in Taylor series

I have a question about rounding error. I have created a function to approximate exp(x) by summing the terms of its taylor series until the sum stops changing. (That is, 1 + x + x^2/2! ...). This ...
2
votes
2answers
85 views

Solving second-order ODEs with Taylor series approximation of second derivative and linear algebra

I was told about an algorithm to solve ODEs which I thought was very clever. I am sure its not something new. It works by discarding the $\mathcal{O}(h^2)$-term from the usual formula for computing ...
1
vote
1answer
90 views

Check if a given polynomial is primitve

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 ...
11
votes
3answers
368 views

Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

One is required to find power (positive integer) of matrix of real numbers. There are lots of efficient matrix multiplication algorithms (e.g. some parallel algorithms are Cannon's, DNS) but are there ...
2
votes
1answer
630 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 ...