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

2
votes
3answers
62 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
39 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
41 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
149 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
50 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
1answer
40 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, ...
2
votes
1answer
72 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
69 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
90 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 ...
0
votes
0answers
39 views

A dynamic programming solution to the bitonic euclidean traveling salesman problem [closed]

This question has been answered here: How to implement a dynamic programming solution to the 2D bitonic euclidean traveling salesman problem? but it didn't quite cover everything I needed. In my ...
1
vote
1answer
60 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
113 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
58 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
59 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
62 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
43 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
27 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
87 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
20 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
121 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
137 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
153 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
76 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
129 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
62 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 ...
1
vote
1answer
88 views

What is the name of the optimization algorithm that uses random sampling?

I am generating random weight as per e.g. below. The I generate a set of 3 values say 100, 250, 300 and I multiple them with the weights below Initial population. ...
4
votes
1answer
118 views

constrained minimization in N dimensions

I am looking to create an algorithm to minimize an N dimensional problem. I am unsure how to write it in its generic form, so I will show it in 1, 2 and 3 dimensions Minimize $ \sum_{i} x_i\left [ ...
1
vote
1answer
79 views

Practices to convert computer algorithms to matheamtical notations [closed]

First, an example: Given an image (2D array) to write down a mathematical notation for the function of pixelation, for example. Fig. 0: The pixelated version (right) of the given 2D array (left) ...
2
votes
1answer
73 views

Optimal algoritm of gcd with complexity

I want to know the best optimal algoritm of gcd with its complexity if you have a any useful source I will be glad to have a look at it.
0
votes
0answers
51 views

Quadratic programming problem involving permutation matrices

Does anyone know a good algorithm for quickly finding an approximate solution to the following problem? Given two square matrices $A$ and $B$, minimize $\| P A P^\top - B \|$ over all permutation ...
7
votes
2answers
184 views

Can one outperform Cramer's rule for the inversion of a 3 by 3 matrix

I know that for general matrices, Cramer's rule is far from ideal for the numerical computation of the matrix inverse. However, can it be outperformed in the case of a $3 \times 3$ matrix? One ...
1
vote
1answer
28 views

Line scan in a 2D histogram

So I have a 2D histogram, in the third dimention are the counts. What I want to achieve is by choosing two random position, make a plot of a 1D histogram along the line that passes through the two ...
1
vote
1answer
73 views

Ray tracer : create an uniform grid [closed]

I wrote a simple ray tracer, and now I try to implement an uniform grid. There is a lot of documentation on how to traverse the grid, but I don't know how to construct the grid. I have my uniform ...
2
votes
1answer
85 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 ...
0
votes
0answers
72 views

Help in developing a dynamic programming solution to this problem

I have asked this question on programmers.stackexchange but nobody was able to answer this question.I have asked for help on other forums but did not get much help.Since this is a part of my research ...
10
votes
1answer
173 views

Numerical methods for inverting integral transforms?

I'm trying to numerically invert the following integral transform: $$F(y) = \int_{0}^{\infty} y\exp{\left[-\frac{1}{2}(y^2 + x^2)\right]} I_0\left(xy\right)f(x)\;\mathrm{d}x$$ So for a given $F(y)$ ...
2
votes
1answer
78 views

Detect rigid body motions in a cloud of points

This question popped up today in our group meeting. Suppose you are given a cloud of N points in 2D and each is associated with a velocity vector. These points are associated with particles on a 2D ...
2
votes
1answer
47 views

Algorithm to extract the decaying parts of complex exponentials

I have an oscillatory, decaying function that can be decomposed as $$\sum_k e^{iz_kt} $$where $z_k$ are complex. What I want is the imaginary parts of all of the $z_k$'s with some range of real ...
7
votes
3answers
238 views

Algorithm to compare two large sets

I am a novice in the world of algorithms, ignorant of the taxonomy used.Please pardon me. I have two large sets of numbers A and B where A = {x| 0< x< 9999999999 } B= {y | 0 < y < ...
0
votes
0answers
23 views

Minimum space occupancy by packing items of variable dimensions

I have a series of indivisible items (boxes) with 3 dimensions (height, length, width). I have to pack them together in order to compute the dimensions of the (or one of the) minimum volume box that ...
0
votes
1answer
418 views

Vertical and horizontal segments intersection (Line Sweep)

Introduction: I have a vertical segment S That i want to move across a plane (Left --> Right), and find intersections with horizontal lines. Problem : The problem which i am having is the ...
3
votes
0answers
97 views

Sound Waves Simulation in 3D Environment

I want to do a simulation of sound waves including wave propagation, absorption, and reflection in 3D space. I did some research and I found this question in stackoverflow but it talks about ...
3
votes
2answers
49 views

sequentially sampling an n-dimensional space

lets say I have a 5 dimensional grid where each dimension has 10 points. There are 100000 combinations. Let's say I want a subset of 10000, is there a deterministic algorithm that will choose a set of ...
3
votes
1answer
56 views

Modification of Levinson algorithm for hermitian toeplitz matrix

I have implemented Levinson algorithm for toeplitz matrix by book: Blahut "Fast algorithms for digital signal processing". Book said - modification of this algorithm for Hermitian matrices is simple ...
0
votes
1answer
90 views

Line segment straddle

What is exactly the definition of "Straddle"? Can you please explain what do they mean exactly or a sketch? A segment P1P2 Straddles a line if point P1 lies on the one side of the line and point P2 ...
2
votes
1answer
144 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 ...
1
vote
1answer
94 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) ...
1
vote
4answers
326 views

How to produce visually unexpected results?

Below is a totally made up example. So let's say on the left we have a weird black-white image or, in other words, a matrix of zeros and ones. We then apply a specific algorithm to the given ...