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 [algorithms]

A description of the specific steps needed to solve a particular problem in an unambiguous way, expressed in an abstract form.

-3
votes
1answer
248 views

Comparison between CashKarp Method and Dormand Prince Method - Runge Kutta Method

Can Cash Karp Method be used for integrating a nonsmooth solution ?. Because Dormand Prince method gives an error while integrating nonsmooth solution How can nonsmooth function can be integrated? I ...
1
vote
1answer
50 views

Literature on comparing Simplex and Interior-Point-Methods (or combining both of them)

Do you know some interesting literature concerning the comparison of Simplex and Interior-Point-Methods referring to linear optimization? I also read about the possibility of combining both of them ...
1
vote
1answer
136 views

What are the prominent algorithms for solving systems of linear inequalities?

Why, you may ask? The Python sympy symbolic library provides solutions to single, linear Diophantine equations in terms of parametric variables. For instance, ...
0
votes
1answer
248 views

Min supporting line for a set of points

I'm trying to solve exercises of the book "Computational Geometry in C" by O'Rourke. Could you please help me with this one? Design an algorithm to find a line $L$ that: has all the points ...
1
vote
1answer
87 views

comparison of CPU time and normalization

How to normalize the CPU time for comparing algorithm execution time on systems with different hardware configurations?
1
vote
1answer
924 views

Simple finite volume method for compressible Navier-Stokes equations

I am interested in writing a simple, cell-centered, 2D FVM code for the unsteady, compressible Navier-Stokes equations (including shocks). Most of my experience is with finite difference and finite ...
1
vote
0answers
24 views

Chinese character component-based layout engine algorithms [closed]

I am looking for a PDF describing Chinese character component-based layout engine algorithms. These should allow for recursive encodings of radical and non-radical components, and the encodings should ...
2
votes
1answer
79 views

Performing computations over the set of constructable numbers

The set of constructable numbers is commonly defined in one of two ways: the set of finite numbers reachable from the rational numbers through a finite sequence of addition/subtraction, ...
1
vote
1answer
98 views

What is a good algorithm, and framework, to calculate centres of gravity or mass (cog)?

I'd like to take an photograph, subdivide it into a tesselation, either of squares, or (ideally), hexagons, and then find the centre of gravity (or, if you prefer, centre of mass) of each cell of the ...
1
vote
2answers
78 views

Iterative root finding of 2-dimensional system of non-linear equations with monotonicity properties

Let $f(x,y)$ and $g(x,y)$ be two $\mathbb{R}^2\rightarrow\mathbb{R}$ functions, both strictly increasing in both arguments. Assume that they are well-behaved functions (continuous, differentiable, etc....
1
vote
2answers
303 views

Defining a pixel neighborhood in an array in MATLAB

I am working with matrix operations in MATLAB, and I would have the following problem. I have matrix containing zero elements: a=zeros(100,100) and another ...
2
votes
1answer
865 views

Applying the result of Cuthill-McKee in SciPy

I have applied SciPy's implementation of the Cuthill-McKee algorithm to a $48 \times 48$ sparse non-symmetric matrix in Compressed Sparse Row (CSR) format and the output is an array of length $48$ ...
1
vote
0answers
57 views

Efficiently computing the properties of a Chebyshev series

Suppose we have some function $f(x)$ defined as a Chebyshev series up to order $M$: $$ f(x) = \sum_{n=0}^{M} c_n T_n(x). $$ For a given coefficients vector $\mathbf{c}$, and $x \in [-1,1]$ I'm ...
1
vote
0answers
30 views

Find alternative path closest to original

I have a set of points in a 2D space. I want to connect the outer points so I get the convex hull. The problem here is that there is a limit to the distance between two points. Let me clarify that ...
1
vote
0answers
37 views

Formation sketching; trouble with sampling unit optimization

I'm looking for assistance in understanding a concise portion of a paper that involves a quadratic equation, so that I can properly implement it. There are 2 versions of the paper. Each paper ...
3
votes
0answers
166 views

logsumexp with one very large term and many very small terms

I want to compute an expression of the form: $$L = \ln\sum_i e^{x_i}$$ Suppose that there are many small terms, say $e^{x_i} \approx \epsilon$. If there are $N_\epsilon$ such terms, their ...
4
votes
0answers
101 views

Stable computation of $\log\sum x_i$ from $\log x_i$, with many terms

Kahan's summation algorithm is a method to compute sums: $$\sum x_i$$ with many terms, without significant error. I want to do this with very large numbers, and instead of the numbers themselves, I ...
3
votes
1answer
609 views

Nearest Neighbors in radius via Z-order order curve?

Given a $M\times M\times M$ 3D cube grid $C$, how can I map the 3D grid-coordinates to 1D coordinates such that every cell's nearest neighbors can be represented by a continuous range of corresponding ...
1
vote
2answers
95 views

What is meant by “operations”?

In this paper, on page 243, we have $$d_{jk} = \frac{a_j}{a_k(x_j - x_k)}$$ where $$a_k = \prod_{l = 0;l\neq k}^{N}(x_k-x_l)$$ Now, $a_k$ requires evaluating N multiplications. Why does the author ...
1
vote
0answers
59 views

Gauss Seidel moving mesh AMR hamilton Jacobi

I was trying to implement a moving mesh algorithm using Gauss Seidel, so: I have a pde like this (Hamilton - Jacobi eq) $\begin{cases}\phi_t+H(\phi_x)=0 & [-1,1]\times [0,T]\\\phi(x,0)=\phi_0 &...
0
votes
1answer
186 views

Heat Equation in 3D mass Matrix set-up

I am solving a 3D heat transfer equation with variable boundaries (insulated, convective, radiative or free) using a F.D.M. technique. My geometry of choice is a cube. The purpose of my work is to get ...
1
vote
0answers
27 views

How to calculate multi-class prediction probabilities using One vs All and One vs One classifiers

To be specific, let's consider Support Vector Machines. In the 1 vs all case, one has $n$ binary classifiers where $n$ is the number of classes. In each classifier one has two labels 0, 1 and for a ...
3
votes
1answer
174 views

Efficient algorithm for a matrix product

Recall that a unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ is a lower triangular matrix with diagonal elements $e_i^{T}L e_i = \lambda_{ii} = 1$. An elementary unit lower triangular ...
1
vote
1answer
67 views

Looking for an accurate algorithm to find the area of a oscillatory function

As the title suggests, I'm looking for a very accurate algorithm to find the area under an oscillatory function. For instance, I would like to integrate the following graph I'm currently using ...
3
votes
0answers
149 views

Solving a 3D (almost radial) convolution with FFT

I have a 3D integral that is almost a radial convolution of the form $$ \int d^{3}k'h(\mathbf{k'})g(|\mathbf{k-k'}|) $$ and I am looking for a fast and efficient algorithm (e.g. FFT) to solve it ...
0
votes
1answer
77 views

$LU$ Factorization of a nonsingular matrix with a particular pattern

Consider $S\in\mathbb{R}^{n\times n}$ whose nonzero elements have the following pattern for $n = 8$: $$\begin{pmatrix} 1 & 0 & 0 & 0 & \mu_1 & 0 & 0 & 0\\ 0 & 1 &...
3
votes
2answers
246 views

2D Laplace problem with mixed boundary conditions using Conjugate Gradients

I am being asked for one of my classes to solve 2D Laplace equations with mixed boundary conditions using the Conjugate Gradient method. The equations and conditions are given as: $$ \frac{\partial^...
0
votes
1answer
179 views

Notations for algorithmic complexity in elementary operations

I am comparing several algorithms (moments and matrix products) for real-time computing in terms of numerical complexity in elementary operations. [EDIT] Algorithms are very similar in terms of ...
3
votes
0answers
36 views

Finding errors in frequency from a Fast Fourier Transform from Gaussian fitting

I took a FFT of sound in a box generated by a frequency sweep over a range of frequencies, and have an array of frequencies and their corresponding FFT amplitudes. According to models for the ...
0
votes
2answers
42 views

Grouping Boolean vectors by similarity up to a rotation [duplicate]

I'm looking for an algorithm to take the entire vector space of length n Boolean vectors and partition it into vectors that are the same up to a rotation of the entries. For example if n=3 the ...
1
vote
1answer
78 views

computational complexity for computing perimeter of a polygon

What is computational complexity for computing perimeter of a polygon of $n$ vertices? The polygon is not necessarily regular and can be convex or non-convex.
1
vote
1answer
134 views

What PRNG function is this?

This is a 16-bit PRNG function, transcribed from assembly to C for easier reading: ...
2
votes
0answers
49 views

SPECT reconstrction using MLEM

In Single-Photon Emission Computerized Tomography (SPECT) parallel beam reconstruction using Maximum-Likelihood Expectation–Maximization(MLEM), is it sufficient to scan the object around 180 degree? ...
0
votes
2answers
116 views

Adaptive numerical integration of a univariate vector integrand

Background & Problem formulation I'm trying to write a simple program in C++ that performs adaptive numerical integration of vector valued integrands (in one variable), i.e. $$\int_a^b \bar{f}(...
2
votes
0answers
381 views

Exact line Search in Steepest descent

I wanted to clarify the idea of the exact line search in steepest descent method. An exact line search involves starting with a relatively large step size ($\alpha$) for movement along the search ...
1
vote
0answers
173 views

Preconditioned Steepest Descent

For my program assignment I need to write a preconditioned steepest descent algorithm. I have psedo-code from my professor which is here: From reading in my text on this method they say that $P$ is ...
3
votes
1answer
221 views

Methods for solving rectangular, full-rank systems of equations — which is best?

Suppose I have a large, sparse, $m \times n$ matrix $A$, with $m \gt n$ and $\text{rank}(A) = n$. I wish to solve $Ax=b$. Suppose I know that $A$ has the following characteristics: $A$ is somewhat ...
8
votes
1answer
747 views

What is the state of the art algorithm for diagonalizing real symmetric matrices?

There are many methods for diagonalizing matrices, probably the most widely used is the combination of Householder transformations and the QR algorithm. Is there any superior method for diagonalizing ...
5
votes
1answer
150 views

Striking examples of success of local search algorithms

In N queens problem https://en.wikipedia.org/wiki/Eight_queens_puzzle, trying to find solution by backtracking encounters difficulties quite fast (even for SWI-Prolog, http://swish.swi-prolog.org/...
5
votes
1answer
169 views

Question on speed and accuracy comparisons of different 2D curve fitting methods

This may be a trivial question, and I apologize if so. Consider the following simple problem: We have a 2D, regular grid of points (say $X = [0,5000] \times [0,5000]$) spaced uniformly by units of 1 (...
8
votes
1answer
489 views

Finite difference recursion and higher order

This may be a trivial question, but I've always wondered... For the classical, central finite difference schemes, if I'm interested in determining the second derivative, does applying the first ...
1
vote
0answers
93 views

String search algorithm on small alphabet

I am looking for an algorithm to search a substring in a string. I know there are a number of wellknown Algorithms like Knuth-Morris-Pratt, for instance, and I suppose most preimplemented functions ...
0
votes
1answer
96 views

Optimizing multiple output parameters for a given input

Problem statement: I'm trying to solve a problem statement using C# as programming language. In the problem system for an input (double/decimal) say $H_i$, the output generated is a form of dataset ...
7
votes
2answers
1k views

Markov (Chain) image generators?

Markov Chains can be used to generate, or auto-complete, text. https://en.wikipedia.org/wiki/Markov_chain#Markov_text_generators Training text is read, and some information about the text is ...
2
votes
1answer
199 views

Help understanding and implementing fast multipole method for N-body

I've been trying to understand the Fast Multipole Method but not really getting anywhere. It seems like the fastest mainstream N-body simulation algorithm, and I would like to implement it in an ...
8
votes
1answer
386 views

N-body simulation optimisation, looking for name or existing work

during the development of my N-body simulation with visualisation in WebGL, I devised an optimisation, and I'm wondering if it has a name. I find it unlikely that it has never been done before. It ...
1
vote
1answer
262 views

I need to deconvolve the image of a fluorescent bead without the Point Spread Function in MATLAB

I am aware that I could use deconvolution algorithms such as LUCY, Weiner and Blind but I am confused as to how to estimate the PSF (point spread function), which is needed for the LUCY and Weiner ...
1
vote
1answer
133 views

Round-robin pairings: Everybody need to meet everybody

I have the following problem, I have a class of N people and I want them to do stuff by pair, but I want them to do this with everybody but as fast as possible. For N = 4 I got this: ...
1
vote
0answers
647 views

Divide and Conquer division algorithm explained (as used in GMP bignum)

I am trying to understand the divide and conquer division algorithm that is used in the GMP bignum arithmetic library. The code is very optimised and that makes it somewhat hard to understand. the ...
0
votes
1answer
72 views

For finding the track of an object through space(3d) over time, what is the correct slope equation to use in the algorithm?

I am working on a program that tracks a flying object through space and predicts the future position of said object. I was given some equations to use, but some of them do not look right, mainly the ...