The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
1answer
60 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
161 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
81 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
34 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
49 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
26 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
26 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
91 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
97 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
43 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
71 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
32 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
565 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
93 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
42 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
967 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
31 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
60 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
528 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
54 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
71 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
48 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
104 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
113 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
98 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
564 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
81 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
33 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
88 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
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 ...
1
vote
2answers
149 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
36 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
89 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
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 ...
8
votes
3answers
4k 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 ...
4
votes
3answers
153 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
43 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
125 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 ...
2
votes
1answer
400 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
67 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
69 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
196 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
522 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 ...
2
votes
1answer
140 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
219 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
616 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
36 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
286 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} \...