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

1
vote
0answers
10 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
0answers
71 views

Efficient algorithm for a matrix porduct

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 ...
0
votes
1answer
51 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
1answer
101 views

Determine a sufficient condition for a Hessenberg matrix to be nonsingular

Consider $A\in\mathbb{R}^{n\times n}$ whose nonzero elements are restricted to the main diagonal the strict upper triangular part, and the first subdiagonal. For $n = 8$ the locations that must be ...
3
votes
0answers
34 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
42 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 &...
0
votes
0answers
17 views

Determine an algorithm for $LU$ factorization and determine the number of operations

Suppose that $A\in\mathbb{R}^{n\times n}$ is a nonsingular matrix and that $A = LU$ is its $LU$ factorization. Give an algorithm that can compute, $e_i^{T}A^{-1}e_j$, i.e., the $(i,j)$ elements of $A^{...
3
votes
2answers
58 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
0answers
29 views

How to do distributed combinatorics

I'm trying to write what I thought would be a relatively simple distributed program for trying out all possible combinations of items in a list to find the optimal combination. I hit a snag when I ...
0
votes
0answers
35 views

lbfgsb quit at the first iteration

Recently I've been working on the implementation of an algorithm, which need me to solve a bounded optimization problem with quality constraints. So I downloaded a Matlab wrapper for lbfgsb. It is L-...
0
votes
1answer
57 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
20 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
0answers
20 views

Algorithm to group Boolean functions by rotation similarity

I'm looking for a way 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 partitions ...
0
votes
2answers
20 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 ...
0
votes
0answers
24 views

Will Golden Section Search work for optimizing weakly unimodal functions?

Will Golden Section Search work for optimizing weakly unimodal functions? If not is there any variation of it that will allow for optimizing weakly unimodal functions instead of strictly unimodal ...
1
vote
1answer
53 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
95 views

What PRNG function is this?

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

multivariate root finding in a finite domain

I am looking for an algorithm that is able to find a root of two-dimensional function in a finite domain. I have the following function: $$G(x,y) = \left[f_{1}(x,y), f_2(x,y) \right]$$ and I want to ...
0
votes
0answers
35 views

How to vectorize the GCD algorithm in number theory

In Python there numerous ways to compute the GCD (Greatest Common Divisor) in Python. Here is one: ...
2
votes
0answers
25 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
0answers
18 views

Adaptiv numerical integration of a univariate vector integrand

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

Finding the one solution of a nonlinear system of equations, using default values if under-constrained

I'm not sure if this is a math question or a programming question, but it is scientific computation so I hope it fits here. I have a system of equations in which I can symbolically solve any ...
1
vote
0answers
43 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 ...
0
votes
0answers
55 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
63 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
143 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 ...
3
votes
0answers
77 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
89 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 (...
7
votes
1answer
127 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 ...
0
votes
0answers
42 views

Testing algorithm on random data

This might be a simple, but then easy to answer, question. I want to test different settings of an algorithm for solving integer programming problems. I have a number of instances from "the real world"...
1
vote
0answers
36 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
0answers
46 views

Sigma scaling problems [closed]

I'm developing an evolutionary genetic algorithm for which I am to use sigma scaling in order to scale the fitness evaluation of the individuals before selecting mates. Sigma scaling of fitness for ...
0
votes
1answer
42 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 ...
1
vote
0answers
41 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
54 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
96 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
64 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
113 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
99 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
63 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 ...
1
vote
2answers
48 views

Maintain Uniform Distribution across Subranges

Note: this is a continuation of Generate Random Number outside Bounds. I have a function (thanks to the previous question) with the following prototype which returns an integer in the range $[0,b]$, $...
0
votes
1answer
25 views

Calculating adjacency matrix of platonic solids

I need to devise a algorithm (in Python) that calculates adjacency matrices for the platonic solids. Inputted into the algorythm needs to be the number of polygons meeting at each vertex and the ...
4
votes
2answers
113 views

Generate Random Number outside Bounds:

Say I have a random number generator that generates a number within [0, RAND_MAX], and RAND_MAX < UINT_MAX. How do I ...
5
votes
2answers
99 views

How to read the number of periods of this complicated graph?

I have two data sets that are quasi-periodic. They have the same period and can be seen clearly by eye. For example when $x\in(100,200)$, both of them have about 32 periods. Below is a zoom-in of ...
4
votes
1answer
67 views

Balancing number of points in a 2D grid

In a parallel MPI code, I have load balancing issues. My 2D computational domain is distributed on a 2D MPI Cartesian topology, which leads to equal sized 2D sub-domains per MPI process. However, the ...
3
votes
2answers
224 views

Solving a system of linear equations with only an approximate solution

I have a system of linear equations that is derived partially from experimental data. Theoretically, the system should have a single, exact solution; however, experimental error causes it to not have ...
1
vote
1answer
123 views

Calculate the area and perimeter of a hand-drawn shape

I need to know whether my idea for my final year project could be achieved or not. If its achievable please guide me with the relevant language and other frameworks. The idea I have a piece of paper ...
2
votes
2answers
110 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 ...
0
votes
0answers
57 views

How do I remove ripples from a reflected image - as in a pond?

If I have a photograph of a reflection in a pond. How do I recover the image reflected? I've attached an example. What would I need to do to recover the bridge that it reflects? I'm full aware that ...
0
votes
0answers
11 views

ROC curve x axis won't reach 1

I am trying to evaluate a classifcation approach based on thresholds, the idea being that whenever a probability of an observation falls into a certain interval, it is considered a success. I have ...