All Questions

Filter by
Sorted by
Tagged with
1
vote
1answer
286 views

Fast Algorithms for solving sparse LP problems

For solving a very sparse LP: {min $cx$: s.t.: $A_{m \times n}x=b$ , $x\geq 0$}, which one of the following algorithms is faster? Logarithmic barrier method Other variants of the interior point ...
2
votes
1answer
82 views

Rational LP to integer LP

In the worst case complexity analysis of all the polynomial algorithms in linear programming such as ellipsoid method and interior point method, there is an assumption that the input data must be ...
11
votes
2answers
3k views

Eigenvalue decomposition of the sum: A (symmetric) + D (diagonal)

Suppose $A$ is a real symmetric matrix and its eigenvalue decomposition $V \Lambda V^T$ is given. It is easy to see what happens with the eigenvalues of the sum $A + cI$ where $c$ is a scalar constant ...
6
votes
2answers
4k views

When to stop Gauss-Seidel-iterations?

I want to have an estimation, that my solution has an error, let's say less than 1e-8. Usually, I stop the Gauss-Seidel algorithm, when the residual is "small enough" and this is already the problem. ...
9
votes
2answers
1k views

Is there an algorithm to find an almost-convex hull given a tolerance angle?

I'd like to know if there is an algorithm that given a set o points and an angle computes the convex-hull if the angle is $\alpha = 0$ and given an $\alpha > 0$ computes an envelope that follows ...
6
votes
1answer
236 views

How far is a non-symmetric discretization of an elliptic operator from the continuous operator itself?

I am investigating the accuracy and stability properties of a non-symmetric discretization of a Poisson problem. The problem originates from a ghost fluid discretization of the projection step of a ...
2
votes
0answers
1k views

Can post-processing use topoSet and createPatch without screwing up the results?

I would like to use patchAverage to obtain the average pressure on an object that consists of multiple patches (due to different boundary conditions), however ...
9
votes
3answers
1k views

Basin of attraction for Newton's method

Newton's method for solving nonlinear equations is known to converge quadratically when the starting guess is "sufficiently close" to the solution. What is "sufficiently close"? Is there literature ...
3
votes
3answers
939 views

Is busy waiting on both MPI_Iprobe and MPI_Testsome efficient?

I have an MPI application that needs to asynchronously respond to both incoming messages and request completions inside a dedicated communication thread. The obvious way to do this is a busy wait ...
10
votes
3answers
1k views

Explicit Euler method too slow for reaction-diffusion problem

I am solving Turing's reaction-diffusion system with following C++ code. It is too slow: for 128x128 pixel texture, acceptable number of iterations is 200 – which results in 2.5 seconds of delay. I ...
11
votes
1answer
723 views

Solving huge dense linear system?

Is there any hope in solving the following linear system efficiently with an iterative method? $A \in \mathbb{R}^{n \times n}, x \in \mathbb{R}^n, b \in \mathbb{R}^n \text{, with } n > 10^6$ $Ax=...
5
votes
1answer
876 views

Convex polytope volume and centroid calculation

I have troubles imagining how to compute a volume and centroid of an n-dimesional convex polytope. For a polygon (especially for convex polygon) the area and centroid are described in (wiki) by $$ A=...
8
votes
2answers
2k views

Nonblocking version of MPI_Barrier in MPI 2

I have a bunch of MPI processes exchanging request messages back and forth. Processes do not know which other processes will send them messages, or how many. Given this situation, I want an ...
8
votes
2answers
219 views

How should I report profiling/timing information about my code?

I've seen a lot of publications in Computational Physics journals use different metrics for the performance of their code. Especially for GPGPU code, there seems to be a great variety of timing ...
30
votes
7answers
7k views

Alternatives to Journal of Computational Physics

The Journal of Computational Physics has been an important outlet for computational science in the past, and I have published there before. For the benefit of those (like me) who have signed the ...
8
votes
1answer
2k views

Finite difference coordinate transformation for spherical polar coordinates

I have part of a problem that is described by the momentum conservation equation: $\frac{\partial \rho}{\partial t} + \frac{1}{\sin\theta} \frac{\partial}{\partial \theta}(\rho u \sin \theta) =0$ ...
6
votes
3answers
138 views

How can I detect which among N bodies with different velocities will collide?

Suppose I have N different airplanes traveling on a two dimensional rectangular plane of size 400km x 400km (i.e. it is as if all planes travel at the same altitude). Assume each airplane has a ...
17
votes
5answers
7k views

What is the best way to determine the number of non zeros in sparse matrix multiplication?

I was wondering whether there is a fast and efficient method to find the number of non zeros in advance for sparse matrix multiplication operation assuming both matrices are in CSC or CSR format. I ...
4
votes
1answer
146 views

Properties of a Shockwave in Fluid Calculations

The comments on the accepted answer of my previous question here have left me with a more general question about accurately capturing shockwaves in fluid calculations. For the sake of having an ...
6
votes
2answers
1k views

Simulating the MPI_Isend/Irecv/Wait model with one-sided communication

I have a MPI computation with the following structure: each processor has a large region of read-only memory divided into chunks. During a compute epoch, each processor performs a (different) number ...
4
votes
1answer
3k views

Shearing and Hartley's rectification

I'm using Richard Hartley's rectification algorithm to rectify a pair of images before performing stereo disparity computation. The problem is I'm observing shearing in one of the rectified images and ...
0
votes
1answer
555 views

Min-cost flow problem

Consider a min cost flow problem in a directed graph $G=(V, E)$ as follows: (*) Min $\sum {c_{ij}f_{ij}}$ s.t.: $\sum_{j\in out(i)}{f_{ij}} - \sum_{j\in in(i)}{f_{ji}} =b(i)$ for each $...
4
votes
1answer
91 views

Linear programming boundedness

Assume the optimal value of a primal problem is bounded. Is the following statement true? If the primal problem is bounded, then its dual problem is bounded as well.
11
votes
1answer
313 views

For software submitted to ACM TOMS, how does the ACM software license agreement interact with other licenses?

The journal Association for Computing Machinery Transactions on Mathematical Software (ACM TOMS) publishes many articles on numerical algorithms that include software implementations. According to ...
3
votes
1answer
664 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. ...
6
votes
4answers
29k views

Ordering of Eigenvalues and Eigenvectors in MATLAB

The following MATLAB function produces the Eigenvalues and Eigenvectors of matrix X. ...
8
votes
3answers
8k views

What norm to choose when?

Recently, I saw this question: how to measure the error of a finite difference method I am student of simulation sciences and unfortunately, for me, it's totally unclear, what norm to use in what ...
1
vote
1answer
87 views

Debugging Shell matrix

I am trying to solve complex valued Poisson equation $$(C + \nabla. D \nabla )u = f \text{ ;where C, D, u and f are complex numbers.} $$ I am breaking this eqn into real valued problem, which is of ...
1
vote
2answers
277 views

Smoothing the diffusion coefficient to improve convergence

I have been reading a book by Thomee and he considers the case of $u_t=(au_x)_x$, for the case of $a$ possibly being discontinuous. Then he says that the problems with convergence might occur, and ...
10
votes
3answers
2k views

Thrust for GPU programming

I'm very new to GPGPU programming so please forgive me if the question is not particularly appropriate. From what I understand GPU programming is a very intricate piece of engineering work when ...
6
votes
3answers
464 views

How to solve a small least-squares problem

This question is not very deep. Suppose I have a small rectangular matrix $A$, with number of rows and columns between $50$-$100$, respectively. Given a right-hand side $b$, I want to solve the least-...
7
votes
3answers
825 views

analyze stability on a nonuniform grid

Assume you have a stability constraint between the space distance in time and space, for example, with an explicit Euler method for $u_t=u_{xx}$ we know $\tau\leq h^2/2$. That is, one can do stability ...
4
votes
2answers
195 views

Finding dominant eigenvectors of an operator that is small but costly to evaluate

Suppose I have a symmetric linear operator $A:\mathbb{R}^k \rightarrow \mathbb{R}^k$ where $k$ is "small" (eg., $k=100$), and I want to find it's first few eigenvectors, (eg., $10$ eigenvectors). If ...
3
votes
3answers
2k views

Inverse of a 10X10 antisymmetric matrix

I want to invert a 10X10 antisymmetric matrix in Python around 10,000 - 20,000 times. Is there a faster way to do it other than to use the built-in inverse function in Python? Thanks.
5
votes
2answers
633 views

Methods to solve a double integral

I want to solve the following expression (used to obtain an analytic solution to a current distribution inside a workpiece): $$a_{mn} = -\frac{\frac{4}{ab} \int_0^a \int_0^b f(x',y')\sin(px')\sin(qy')...
1
vote
2answers
1k views

What does “Counting algebraic multiplicity” mean?

As stated in the title, I encountered a proof with the final statement of the form "the eigenvalues of A are then $\{\lambda_1+c, \lambda_2, \dots, \lambda_n \},$ counting algebraic multiplicity. ...
0
votes
1answer
283 views

Quickly computing inversion of a large sparse partial stochastic matrix

Suppose I have a sparse stochastic matrix $M$ (with thousands or millions of stochastic column vectors), possibly encoding some links in a web graph. Now I split it into two matrices: $D$ containing ...
1
vote
2answers
160 views

Sparse non-square system of linear equations in exact arithmetic [closed]

What is the best known algorithm for exactly solving a large sparse system of linear equations? The system I'm working on is not symmetric, not positive definite and integer. The only benefit is being ...
13
votes
5answers
445 views

What are the benefits and drawbacks inherent to using classes to encapsulate numerical algorithms?

Many algorithms used in scientific computing have a different inherent structure than algorithms commonly considered in less math-intensive forms of software engineering. In particular, individual ...
2
votes
2answers
543 views

What are d_nz and o_nz in PETSc's MatMPIAIJSetPreallocation function?

I'm working from ex2.c of PETSc's example codes. On line 65, the code specifies: MatMPIAIJSetPreallocation(A,5,PETSC_NULL,5,PETSC_NULL); I looked up the ...
1
vote
1answer
2k views

how to measure the error of a finite difference method

Suppose I am solving a pde with a solution known with a finite-difference method. I can represent it as $A_hu_h=f$ for some approximating matrix $A_h$. And I define the discrete norm in which I will ...
5
votes
2answers
195 views

Is there a special algorithm for computing the convex hull ordering when the candidate points are on the hull?

I'm dealing with a set of points which are already placed on the 2D hull boundary: a convex polygon. I know this for sure. However, the point set is not ordered, and I need the polygon points to be ...
3
votes
3answers
957 views

Spectrum of the product of two matrices

Given SPD matrix $$A \in \mathbb{R}^{N \times N} $$ and positive diagonal matrix $$D \in \mathbb{R}^{N\times N}.$$ What is then spectrum of the product $$D^TAD.$$ Is there a closed-form relationship ...
6
votes
1answer
498 views

eigenvalue analysis vs fourier analysis for stability and their equivalence

I have a question regarding stability analysis for constant coefficient pde. Suppose I am looking at the pde $$u_t= au_{xx}$$ So the first approach is to compute the amplification factor, and this is ...
2
votes
2answers
447 views

Finite volume solution of electrostatics using magnetic vector potential

I would like to solve for the electric potential and magnetic vector potential using the finite volume method (collocated grid). My equations are: $\nabla\cdot(\sigma\nabla\phi)=0$ $\nabla \cdot \...
0
votes
2answers
5k views

BLAS/LAPACK subroutine to add two matrices with different offsets and leading dimensions

I currently searching for a subroutine from BLAS or LAPACK which realizes the following operation A = alpha*A + beta * B where A and B have different leading ...
4
votes
2answers
2k views

Software for 3D Navier-Stokes equation

What is the best software for solving and simulating the 3D Navier-Stokes equation for incompressible laminar non-Newtonian fluid flow?
5
votes
0answers
115 views

How to choose a stable PML for pseudo-spectral method with strongly varying velocity

My friend was working on this, and he asked me about the stability of PML while applying on pseudo-spectral method, I believe his concern was how to choose the difference(if the difference should be ...
6
votes
2answers
547 views

Efficiency of a Dynamic Mesh vs. a Static Mesh for a Propagating Shockwave

I have a low speed flow with a high voltage discharge occurring within it between two spherical electrodes. We have quite a bit of data from the experiment and have performed 0-D modeling of the ...
25
votes
3answers
1k views

Why is the time dimension special?

Generally speaking, I've heard numerical analysts utter the opinion that "Of course, mathematically speaking, time is just another dimension, but still, time is special" How to justify this? In ...

15 30 50 per page
1
159 160
161
162 163
176