Questions tagged [algorithms]

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

Filter by
Sorted by
Tagged with
3
votes
1answer
58 views

Understand the need for Welford's online algorithm

I am puzzled by the Wikipedia entry discussing many online algorithms for computing the sample variance, including the Welford's online algorithm. In particular, the sample variance $s_n^2$ can be ...
3
votes
2answers
249 views

Image hash similarity matching possible?

I have the following question: We have two face image files (JPEG), a Matrix of $128\times 128$ with values between 0-255. We would like to hash both image files using a function $f(x, key)$. Where I ...
3
votes
2answers
415 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^...
3
votes
1answer
80 views

How to Check a Hyper-Cube for Defects

I would greatly appreciate some help/references on solving the following problem: You are in charge of searching through a n-dimensional hyper-cube $[0,1]^n$ to make sure that it does not contain ...
3
votes
1answer
357 views

Computing the (non-convex) boundary of a set of paths between two points

I have a set of paths between two fixed points (marked in red below). Each of these paths consists of an ordered series of $\{x, y\}$ points (marked in blue). I am trying to find the ordered set of ...
3
votes
2answers
375 views

Large binary programming problem

I have 10000 variables (each of them is binary), vector of positive coefficients and a matrix $A$ ($10000\times10000$), if $A_{ij}=1$, then $i$th and $j$th variables can take 1 simultaneously, if it ...
3
votes
2answers
433 views

Best incremental multidimensional Delaunay tessellation algorithm

I'm looking for a specific type of Delaunay tessellation algorithm. The algorithm should be: incremental so that I can add new sites inside known simplexes (i.e. no searching for the right simplex ...
3
votes
1answer
206 views

How to detect specific behavior in time series?

I was not quite sure what the right SE for this was, so I posted this also here on DSP. Please tell me which one to remove :) Problem statement I have a few hundred unrelated time series, say $P_i(t)...
3
votes
1answer
68 views

Suitable algorithm for superposing variable scalar distributions in 2D area with constraints

I'm trying to place multiple light sources on a 2D plane, in a fashion that satisfies multiple constraints. The 2D scalar distributions are the irradiance distributions of each light source that are ...
3
votes
1answer
710 views

In molecular dynamics (MD) simulations, how is particle number density computed in practice?

I have been reading a recent paper. In it, the authors performed molecular dynamics (MD) simulations of parallel-plate supercapacitors, in which liquid resides between the parallel-plate electrodes. ...
3
votes
1answer
420 views

Testing a simple polygon for monotonicity in linear time question

I'm looking for the algorithm of Preparata and Supowit for testing a simple polygon for monotonicity in linear time. I've found it referenced in many textbooks but I can't find the algorithm itself. ...
3
votes
1answer
220 views

Time Reversibility of Velocity Verlet Algorithm

I'm very new to computational Physics and am finding conflicting statements on whether the velocity Verlet algorithm, defined as: $\begin{align} x_{n+1} &= x_n + v_n \Delta t + \frac{1}{2} a_n \...
3
votes
0answers
69 views

Computation of Troullier-Martins pseudowavefunctions

The computation of Troullier-Martins pseudowavefunctions has been described in [1]. The pseudowavefunction $R^{\textrm{PP}}_l$ is defined by $$ R^{\textrm{PP}}_l(r) = \left\{ \begin{array}{ll} R^{\...
3
votes
1answer
113 views

How to find a pair of divisors as close as possible to each other?

For a given integer $n\in\mathbb{N}^*$, I want to find a pair $(x,y)\in{\mathbb{N}^*}^2$ such that $x*y=n$ and $|y-x|$ is as small as possible. A naive algorithm I found is : ...
3
votes
3answers
213 views

Clustering with points lying along different 3D planes

I have a bunch of data points in 3D that lie along a few planes. What would be the best approaches to estimate the normals of these planes? Edit: There are roughly equal number of points lying along ...
3
votes
0answers
96 views

First order methods for a large scale semidefinite program

I am interested in solving the following semidefinite optimization problem: \begin{equation} \begin{split} \underset{X,\lambda}{\rm maximize} \;\;\;\;&\lambda^Tc \\ &-\mathbb{I} \le X \le \...
3
votes
0answers
101 views

Fast Algorithms for the Simplicial Decomposition of a Convex Polytope in N-Dimensions

I'm in the process of constructing an algorithm which computes the Voronoi diagram of a set of points, but I now need a method to decompose each Voronoi cell into simplices. The information we have is:...
3
votes
0answers
332 views

Open source implementation of Multiscale Combinatorial Grouping

I would like to use Multiscale Combinatorial Grouping for my PhD research. However, I am restricted to use open-source implementations and this one runs on Matlab. Does anyone know of an equivalent ...
3
votes
0answers
107 views

How can I evaluate the accuracy of my n-body simulation?

I am making an n-body simulation in python. There are many different methods to numerically solve the system of differential equations governing the gravitational interactions between the $n$ ...
3
votes
0answers
99 views

Computing Algebraic Riccati inequality

In my Robust model control, I have got a couple of quadratic Riccati inequalities which need to be solved numerically on MATLAB. My question, Is there function on MATLAB can solve quadratic Riccati ...
3
votes
0answers
226 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 ...
3
votes
1answer
152 views

similarity/distance measurement between two ranked sequence

Is there an efficient way to measure similarity/distance between two sequences of ranked numbers/letters. The two sequences are of different length, and only have some elements in common? For example,...
3
votes
3answers
1k views

How to solve a Linear Matrix Equation: AX-XA=B efficiently?

recently I have been working on solving some math problems using Fortran. There occurs to me that a linear matrix equation: $$ AX-XA=B $$ where $A$ and $B$ are known $n\times n$ matrices and $X$ is ...
3
votes
0answers
106 views

Find a function's minimizing set of parameters

I have a function defined by three parameters (or variables): $f(a,b,c)$ This function is not explicitly defined but is actually a piece of code which returns the result of fitting a curve $g(a,b,c)$ ...
3
votes
0answers
103 views

Dissipation and symplectic manifolds

I'm working on an API for simulation of port-Hamiltonian systems. As far as I understand it, a Hamiltonian system is symplectic if it is power conserving, and so including resistive elements would ...
3
votes
0answers
76 views

Parallel algorithm to use in place of PORTA?

We currently use PORTA software to find the list of facet-defining inequalities (FDI) for polytopes that we work with. For certain polytopes, PORTA works fine. But because it is a serial algorithm (...
3
votes
0answers
111 views

exact area resampling [closed]

I do image processing, and right now I need to resample some images taken from slightly different perspectives so I can match up features. The pixel intensities have scientific significance, so I want ...
2
votes
2answers
147 views

How does Mathematica compute real and complex solutions to single, non-polynomial equations?

This question on StackOverflow has led me to ask myself what would be involved in solving an equation like this one using tools available to the Python programmer. $$ \frac{0.125567841}{d^{2.25}} = \...
2
votes
2answers
362 views

Generation of random Matrix with Real eigen values

does anyone know any matlab algorithm that can help me generate a random matrix with REAL EIGEN values? Thanks.
2
votes
3answers
252 views

On the reordering of sparse matrices

I have been reading on different techniques used to reorder sparse matrices to achieve better performance, the most popular being the Cuthill-McKee or Reverse Cuthill-McKee algorithm. Most of those ...
2
votes
1answer
189 views

How does Mathematica compute 'Reduce'?

I submit a Reduce command and get results like this: ...
2
votes
2answers
373 views

QR decomposition

I have a matrix which is "almost" like an upper triangular just that the last row has non zero elements. And I want to perform the QR decomposition on that matrix. Does anyone know the "name" of such ...
2
votes
2answers
257 views

Quicksort - difference in time

I'm testing Quicksort based on Niklaus Wirth algorithm. I'm checking how much time I need to sort an array. There is interesting thing that for an array consisting elements in these sequence: 1 3 ...
2
votes
2answers
302 views

Find connected circles

I have a problem as follows: We have a set of circles (we know the radius r and the center point c in Rd of each circle) We ...
2
votes
2answers
955 views

Determining if samples fit a 3D Gaussian distribution

I have a collection of sample particles, with (x,y,z) coordinates generated by a simplified Monte Carlo-like code. I expect that these particles will follow an anisotropic diffusion process, which ...
2
votes
2answers
2k views

Patankar's algorithms for Numerical Heat Transfer and Fluid Flow

I am looking for the algorithm of Patankar (for example, SIMPLE, SIMPLER, SIMPLEC and PISO) written in Fortran for the simulation of heat transfer and fluid flow.
2
votes
2answers
4k views

Implementing PageRank using the Power Method

I am trying to implement the PageRank algorithm described in this paper (Fig. 1). Here is the breakdown of the steps: http://www.louismullie.com/algo.png where: ...
2
votes
1answer
59 views

How to select initial time step in adaptive time step ODE solver (TR-BDF2)

The Problem I am currently reconstructing a TR-BDF2 scheme which contains the following two stages: \begin{align} y_{n+\gamma} & = y_n + \gamma \frac{h}{2}\left( f_n + f_{n+\gamma} \right) \...
2
votes
1answer
651 views

MD Simulation: Reference for the Neighbor's List Method

With a rather basic knowledge in C++, I have written my own MD simulation code. Currently, I calculate forces in the most naive way: I go through all the atoms and account for their interactions. This ...
2
votes
3answers
695 views

Sparse, underdetermined system of linear equations

I'm looking for an algorithm to solve the underdetermined system of linear equations $$\mathbf{A}\,\mathbf{x} = \mathbf{b}$$ with $\mathbf{A} \in \mathbb{R}^{n\times n}$, $\mathbf{b} \in \mathbb{R}^...
2
votes
1answer
1k views

Multivariate Orthogonal Polynomial Generation

I'm trying to apply the stochastic galerkin method to partial differential equation with multiple uniform random coefficients. I'm puzzled as to how to extend the corresponding orthogonal (legendre) ...
2
votes
1answer
118 views

Union of closed intervals on $\mathbb{R}$

Suppose there are multiple intervals on $\mathbb{R}$, e.g., $[0,0.5]$, $[0.4,1]$, $[1.5,2]$, the union of them should be $[0,1]$ and $[1.5,2]$. Is there a specific datastructure (or algorithm) for ...
2
votes
1answer
94 views

Description of algorithm for small scale linear least squares with box constraints

I have small scale dense least squares problem with box constraints $$\mbox{argmin}||Ax - b||^2 \quad $$ $$\mbox{subject to} \quad l_i \leq x_i \leq u_i,$$ Number of variables is about 10-50, ...
2
votes
2answers
847 views

How to choose the number of random points in Monte Carlo simulations?

I am struggling with convergence criteria when performing a Monte carlo simulation on a uniform distribution. Any help would be much appreciated ! Say I want to sample uniformly a 1D interval (for ...
2
votes
1answer
108 views

Parameter reduction algorithm for least square model

Question I am performing least squares fitting using an objective function of the form $f(\mathbf{x})$ where $\mathbf{x}$ is a vector of parameters containing around 20 elements. The model function ...
2
votes
2answers
79 views

Response to quantifying algorithm bottlenecks memory vs. computation.

The number 1 response to this question was great. Is algorithmic analysis by flop-counting obsolete? Now, the only problem is that I don't really understand it. Here's my example of why it's not ...
2
votes
1answer
127 views

combine $n$ vectors using $L2-normalization$

Suppose that I have the following vectors $v_1$, $v_2$, $v_3$ $\in R^n$,$n= 9$. What I want to do exactly is to combine these $3$ vectors into $1$ representative vector $V$. According to the ...
2
votes
2answers
58 views

Clustering Algorithm for a congruence relation?

Say we are given a congruence relation$~\sim$ in a dataset with $n$ elements. I am looking for an algorithm for optimally sorting the $n$ elements into $m$ clusters according to given congruence ...
2
votes
1answer
56 views

Maintain unitary time evolution for a nonlinear ODE

I want to solve a nonlinear ODE of matrix $A(t)$ $$\mathrm{i}\dot A = A(t)M(t),\:\mathrm{with}\: M(t)=A^\dagger(t)H(t)A(t)$$ where $H(t)$ and hence $M(t)$ are Hermitian. Therefore, I presume the time ...
2
votes
1answer
42 views

How do you construct a self-similar binary structured-tree?

Please excuse me if this question somehow looks trivial or not really interesting, but I recently have a hard time to convince someone else that my algorithm for constructing a self-similar binary ...

1
3 4
5
6 7
11