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

learn more… | top users | synonyms

0
votes
1answer
22 views

Appropriate algorithm for (non-linear) ODE with integral equilibrium constraint: collocation?

I have a problem of the following structure: For some scalar $g$, functions $F(z)$ and $h(z)$ defined on $[0,\bar{z}]$ , and a non-linear operator $\phi(F,z)$ (in reality, $F$ and $h$ are vector ...
0
votes
1answer
20 views

Algorithm for distributing members over activites (with individual preferences)

So in my school we have a day where everybody participates in different activities. Each projects can have like 10 members. The whole day is divided in 2 or 3 different blocks, in which the pupils ...
0
votes
1answer
59 views

Finding roots without knowing much about the function

Consider solving numerically for roots: $( x_0, y_0): f(x_0, y_0) = 0, g(x_0, y_0) = 0$ where you only know that f, g continuously differentiable but the theoretical differentiation is not a ...
2
votes
0answers
35 views

Algorithm for optimizing graph interconnectivity

I have a partiuclar kind of graph problem and (not having a background in graph algorithms) I would like to know how this kind of problem is called in the literature and what algorithms exist for ...
0
votes
0answers
15 views

Generation of symmetric groups

I've been trying to make an algorithm to generate symmetric groups in order to create graphics like the ones shown here. I've programmed circular and dihedral groups so far, but could someone help me ...
9
votes
0answers
87 views

Why are Octrees used for Multipole space decomposition?

In most (all?) implementations of the Fast Multipole Method (FMM), octrees are used to decompose the relevant domain. Theoretically, octrees provide a simple volumetric bound, which is useful for ...
1
vote
1answer
35 views

How to compute the weight matrix for tomography applications?

I am trying to compute the weight matrix for a set of straight ray paths through a reconstruction region. Ideally, I would like to be able to do this for both a rectangular grid region, where each ...
0
votes
0answers
42 views

Algorithm for Octree for nearest neighbor seach

Problem Statement: To find the nearest GRID ID of each of the particles using Octree. I have a system of particles(~6k, movable, Fig 1) for which I need to check which grid point (rigid; in ...
0
votes
0answers
49 views

Algorithm to explore a 3D scalar potential

I have to write an algorithm/code to reconstruct an unknown 3D scalar potential $ V(\mathbf{r})$ up to a specified threshold $E_c$ (assume that the potential is monotonic) The problem has the ...
9
votes
1answer
409 views

What are the relative benefits of using Adams-Moulton over Adams-Bashforth algorithm?

I am solving a system of two coupled PDE's in two spatial dimensions and in time computationally. Since the function evaluations are expensive, I would like to use a multistep method (initialised ...
0
votes
2answers
159 views

How can I create a computational model of the human eye?

I need to create a program that can simulate the optical system of the human eye. The input will be any image, the output would be the image that is projected onto the retina. I need it to be as ...
9
votes
3answers
613 views

Is there a complexity between $O(n)$ and $O(n \log n)$ [closed]

Is there a complexity degree that is bigger than $O(n)$ and smaller than $O(n \log n)$?
1
vote
0answers
40 views

Computing a description of a set of lattice points

I have an infinite subset $S$ of $\mathbb{N}^k$ which I know (or at least strongly suspect) is a finite union of regions, each of which is defined by finitely many linear equalities and inequalities ...
2
votes
1answer
112 views

Examples of high polynomial order complexity

I was reading Twenty Questions for Donald Knuth and was intrigued by Knuth's argument in question 17 for why he suspects P=NP. In the discussion he asks why you couldn't have an algorithm bounded by a ...
2
votes
0answers
34 views

Algorithms for adding hydrogens on a molecule

I want to add hydrogens to some linear polymer molecules (polyethylenes). I know some working methods like using PyMOL internal function h_add. This method works, but hydrogens are added at distances ...
0
votes
0answers
30 views

Matching signals in time domain

I would like to ask about methods to match one dimensional discrete signals to given templates. So far I have studied the basics of DTW algorithm, but I do not know if this is the optimal method. The ...
1
vote
1answer
213 views

Is there always a linear iterative alternative to a recursive iterative process? [closed]

This may very well be a silly question but I'm trying to cement my understanding of the material in the SICP (http://goo.gl/QXrbtV). My intuition (common sense) says yes, but wondering from a ...
1
vote
2answers
98 views

How to get ODE solution at specified time points?

The code below basically illustrates my problem. It is a test code for a pendulum. I solve it using a method suggested on ...
1
vote
1answer
100 views

Most memory-efficient way to store a list of numbers

My problem deals with a large $n \times m$ matrix from which I extract and store several square $k \times k$ submatrices. The original matrix may be very large, and I may need to store many thousands ...
0
votes
1answer
182 views

Drunken Man in Matlab

I wrote a script that plots the results of the "drunken lamppost" problem in MATLAB. Now I need to create a road-width from -3 to +3, length from 0 to infinity but the drunk can walk just ahead. It ...
1
vote
0answers
67 views

Solving “virus”, a flash game, in the least amount of attempts

We am currently working on a project related to computational optimization, in which I have tasked myself with calculating the most efficient solution to one of the game's levels. Link to the flash ...
0
votes
0answers
74 views

Dijkstras algorithm-> shortes path problem

Hi i have problem understanding shortest path computation when Dijkstra’s algorithm is applied. Given the graph as depicted below the shortest path from A to G is 42 and that corresponds to ...
3
votes
1answer
133 views

Large binary programming problem

I have 10000 variables (each of them is binary), vector of positive coefficients and a matrix A (10000*10000), if Aij is 1, then ith and jth variables can take 1 simultaneously, if it's 0, then it's ...
1
vote
0answers
23 views

What's the most efficient way to calculate the Wiger quasiprobability distribution?

I want to calculate the Wigner quasiprobability distribution function of a particular wavefunction. The definition suggests a few straightforward ways of calculating it, but I was wondering if there's ...
3
votes
3answers
116 views

Efficient solver for a symmetric tridiagonal system where the upper/lower diagonals are offset

I'm looking for an efficient way to solve a symmetric tridiagonal system $Mx = d$, where the upper and lower diagonals of $M$ are offset from the main diagonal by $k$ rows/columns: $$ \begin{bmatrix} ...
1
vote
0answers
52 views

Lanczos algorithm with thick restart on a dynamic matrix

According to a recommendation, this is a re-post of that. currently, I'm working on a way to compute the 2 biggest eigenvalues of a real, symmetric, huge and sparse matrix that changes a few entries ...
1
vote
1answer
52 views

oSVD and cSVD terms

In one article I faced with such terms as sSVD, cSVD and oSVD. As I understand sSVD - standart SVD, cSVD - svd for block-circulant matrices, but I can't find what is oSVD. 1) What is oSVD? 2) Can ...
3
votes
3answers
178 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 ...
0
votes
1answer
53 views

How to model waterflow when only a couple of sample points available

Figure below depicts a cross section of a creek for which I am trying to measure the water flow for that section. What we have as inputs are a bunch of sample points on the river. For each sample ...
3
votes
2answers
85 views

Finding the minimum hamming distance between a bit vector and any pairwise intersection of multiple bit vectors

I'm looking for a way to optimize this procedure. This is the problem: I have a list of bit vectors $\mathbf{A} = [ a_1, a_2, a_3, ..., a_n ]$ I have a list of bit vectors $\mathbf{B} = [ b_1, b_2, ...
3
votes
1answer
149 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 ...
2
votes
1answer
95 views

Adaptive ODE algorithm in Python

I want to integrate a particle path in 2D using the integrate.ode module. Things that are a bit different in my case are that, I only want to integrate up to a ...
5
votes
1answer
117 views

Finding closed equipotential surfaces on a 3D grid

In short, I'm looking for either: (1) Publications or other sources dealing with contour/isosurface finding algorithms, so that I can write my own implementation (and parallelize as best I can), or ...
1
vote
1answer
73 views

RATTLE numerical integrator example

I want to understand how the RATTLE algorithm works. Can somebody give me an example (in pseudocode or using any programming language like python or matlab) of how would I implement a numerical ...
0
votes
0answers
35 views

how to detect planets in resonance

I make this program, i have a 2xN matrix in which the columns are the ID of planets and their period, the rows are the number of planets, for istance something like that: ...
2
votes
2answers
123 views

Why is computational cost measured in Floating Pt. Ops. in times of parallel computing?

In times of parallel computing, it seems to me that algorithms (also basic ones, like matrix-vector multiplication) should be measured by their dependent steps (that use results from steps before) ...
1
vote
2answers
61 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 ...
0
votes
1answer
84 views

Gilbert-Peierls algorithm for LU Decomposition

I searched for Gilbert-Peierls algorithm, but I haven't found anything useful (well, I found this, but it's not working as it should). I think the problem is the second part, and also that those ...
1
vote
1answer
84 views

Constrained Minimization of Tsallis Entropy

I am looking for finding the velocity distribution using Principle of Maximum entropy when applied to Tsallis entropy. Tsallis entropy is defined as: $$ S_{T} = ...
0
votes
1answer
47 views

Finding maximum value in huge dataset

I am working on a project involving some pattern recognition. For this I need to find the maximum value in a huge multidimensional dataset. For example I have a discrete 5-dimensional space containing ...
2
votes
0answers
32 views

Radial integration of expensive function with Bessel weights

I need to calculate the integral $$I = \int_0^R f(r)J_n\left(\frac{z_{nm}r}{R}\right)rdr$$ where $J_n$ is the $n^{\mathrm{th}}$ order Bessel functions of the first kind, $z_{nm}$ is its ...
11
votes
8answers
1k views

Which algorithm is more accurate for computing the sum of a sorted array of numbers?

Given is an increasing finite sequence of positive numbers $z_{1} ,z_{2},.....z_{n}$. Which of the following two algorithms is better for computing the sum of the numbers? ...
3
votes
1answer
88 views

Updating an approximate solution to a linear system in response to a small change

This question was original posted on SO but it was suggested that I post it here. I'm working on a program in which I have a banded matrix M and a vector b, and I want to maintain an approximate ...
0
votes
0answers
27 views

State variable identification for Ensemble Kalman filter

For those who use the EnKF in a system in which there are a lot of hidden states variable (no observations available for updating because they are not measurable or because they do not have a physical ...
0
votes
2answers
144 views

Algorithm to find non-negative integer solutions to x_1 + x_2 …=n

I know the number of solutions to the equation $$x_1+x_2+x_3+...+x_k=n$$ is given by $\binom{n+k-1}{k-1}$. Is there an algorithm to actually find all the solutions to this equation, without having to ...
3
votes
2answers
159 views

Algorithm for Complete Eigenvalue Problem of a Real Symmetric nxn Matrix

I have a nxn covariance matrix (so, real, symmetric, dense, nxn). 'n' may be very very very big! I'd like to solve complete eigenvalue (+eigenvectors) problem for this matrix. Could somebody tell me ...
4
votes
2answers
221 views

computing the truncated SVD, one singular value/vector at a time

Is there a truncated SVD algorithm that computes the singular values one at a time? My problem: I would like to compute the first k singular values (and singular vectors) of a large dense matrix M, ...
3
votes
2answers
88 views

Affect of approximating a non-differentiable function on optimisation of minimisation

I am looking at a problem of constrained minimization, where the function to be minimized contains the Heaviside function, and as such is not twice continuously differentiable. My question is what ...
2
votes
3answers
139 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 ...
0
votes
0answers
72 views

How to find out if it is possible to contruct a binary matrix with given row and column sums

How to find out if it is possible to contruct a binary matrix with given row and column sums. Input : The first row of input contains two numbers 1≤m,n≤1000, the number of rows and columns of the ...