Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

9
votes
2answers
264 views

Approximation theory on the disc

Chebyshev theory provides a very effective method for approximating continuous real valued functions on the unit interval. Is there something similar for continuous real valued functions on the ...
0
votes
0answers
35 views

Inner Products vs Discretizations of Functions

Let $f:(0,1)\rightarrow [0,1]$ be a $\mathcal{C}^{\infty}$ function. We say that a function $D_r^f:\{1,...,r\}\rightarrow [0,1]$ is an $r$-discretization of $f$ if $$D_r^f(j) = \frac{1}{|a(j)-b(j)|}\...
2
votes
2answers
97 views

Fixed point iteration on symmetric biconvex function

Suppose $X\subseteq\mathbb{R}^n$ is a convex set and that a function $g(x,y):X\times X\rightarrow\mathbb{R}_+$ is smooth, "strictly biconvex" (strictly convex in $x$ and $y$ independently but not ...
8
votes
0answers
795 views

American put option pricing by “binomial trees”

Dear MO World, I'm teaching a financial mathematics course and have found a fascinating (to me) numerical phenomenon and wonder if anyone has studied it, or knows anything similar. I'll try and give ...
-2
votes
0answers
14 views

Why the negative gradient gives the direction of the steepest decrease in the gradient descent algorithm? [migrated]

I understand that the gradient vector gives the direction of the maximum growth. What I don't get is why going the exact opposite direction is going to get the maximum decrease? By sure that holds ...
6
votes
2answers
119 views

Symmetric matrix formula for Gauss-Legendre quadrature

While searching the web, I came across the following algorithm for the Gauss-Legendre quadrature. I wasn't able to find a reference or a proof of my own as to why it works. I'll present it, and the ...
11
votes
2answers
400 views

Computing Gauss Legendre Quadrature for Large N

I've been scanning across the web, and haven't found a good method to compute the Gauss Legendre abscissas and weights $\{ x_j, w^j \} _{j=1}^N$ for large $N\in\mathbb{N}$. My question is how to do it,...
0
votes
0answers
93 views

Does the method below provide any advantages?

I completed course intro to numerical method and lately interested and trying to find special way to solve this ODE.I have try and ask in math exchange stack but do not get any respond so decided to ...
12
votes
14answers
4k views

Basic software libraries for numerical analysis using modern programming languages?

I'm looking for a software library with a scope similar to "numerical recipes", but implemented in a modern programming language. "Modern" in this context means to me: object oriented (not C or ...
0
votes
0answers
80 views

Orthogonal Procrustes problem for sub-spaces?

By Orthogonal Procrustes problem I mean given matrix $A$ and $B$ finding a orthogonal matrix $R$ which most closely maps $A$ to $B$, this has a solution as shown in https://en.wikipedia.org/wiki/...
2
votes
1answer
608 views

How to apply Lagrange Multipliers to BCs of Time Dependent problems using finite elements?

I am trying to implement a finite element scheme using the method of lines (finite difference in time and finite element in space) and enforcing boundary conditions using Lagrange Multipliers. This ...
1
vote
0answers
68 views

Negative eigenvalue of Toeplitz Hermitian matrix?

I am working on estimation of a covariance matrix and I know that the matrix is Toeplitz. The desired matrix should not produce negative eigenvalues at all. However, sometime my estimation leads to a ...
0
votes
0answers
36 views

Proving Fixed Point Algorithms

In Thomas Minka's paper on Estimating the Dirichlet Distribution (link here http://research.microsoft.com/en-us/um/people/minka/papers/dirichlet/minka-dirichlet.pdf), the author presents a fixed ...
7
votes
5answers
1k views

solving Lyapunov-like equation

The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...
3
votes
0answers
61 views

Eigenvalues of approximations to product-convolution operators

Consider an operator $T: L^2 \mapsto L^2$ of the form $TA = g (h \ast A)$ where $g$ is and $h$ are bounded $C^\infty$ functions. This operator $T$ can be shown to be Hilbert-Schmidt, hence compact. ...
0
votes
0answers
42 views

Largest instance of highly nonlinear benchmark functions (e.g. Rastrigin function)

What is the largest instance size (number of variables) ever numerically solved for highly nonlinear (continuous, not combinatorial) optimization benchmarks functions, such as Rastrigin, Schwefel or ...
2
votes
1answer
92 views

A centralised website for computational attempts in graph theory and metric geometry?

The set of questions below stems from this question. 1) does a website exist that contains (at least links to) code and data files, with the aim to centralise computational results in graph ...
7
votes
2answers
2k views

Finding the smallest eigenvalues of a large, but structured, matrix

I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $M$. $M$ is a Laplacian matrix, and it has the following structure: $...
1
vote
1answer
117 views

Looking for tighter bounds on a certain solution of a nonlinear equation

I have to solve an equation which is $$\sum_{i=1}^N x_i = \sum_{i=1}^N y_i,$$ where $$x_i = \frac{z_i}{1 + (K_i - 1) w}$$ and $$y_i = \frac{K_i z_i}{1 + (K_i - 1) w}.$$ The $z_i$ are all positive ...
2
votes
0answers
177 views

Generalized arithmetic progressions contained in Bohr sets

Recall that a generalized arithmetic progression of dimension $d$ is, by definition, a set of the form $P = P_1+\dots+P_d$, where $P_j = \{lp_j\ \mid \ |l|\leq l_j\}\subset \mathbb Z$ is an ordinary ...
4
votes
0answers
92 views

Connection between cardiac equations and untangling knots?

I was surprised to learn that there is (conjecturally) a connection between a cardiac muscle model known as the FitzHugh-Nagumo equations, and untangling knots: Maucher, Fabian, and Paul Sutcliffe....
0
votes
0answers
23 views

Dennis More' Superlinear Convergence_refrences request

Why in the proof of superlinear convergence of restricted broyden class (for the unconstrained optimization) we need the bounded deterioration condition for the approximation of all the true hessian ...
7
votes
1answer
94 views

Fast Fourier Transforms for non-trigonometric bases

The fast Fourier transform allows decomposition into a sin/cos basis in $N \log(N)$ complexity. Can one generalize the algorithm (or the ideas used) to other bases, e.g. orthogonal polynomial bases ...
2
votes
2answers
514 views

What is the definition of an antilimit?

I've seen some references to antilimits in the numerical analysis literature, but no definition of the term. The impression I get is that in specific contexts where every sequence $x_0,x_1,x_2,\dots$ ...
5
votes
2answers
207 views

Alternating binomial Dirichlet series

I have come across the following deceptively simple expression: $$ H_n^s=\sum_{j=1}^n(-1)^{j-1}\left(\begin{array}{c}n\\j\end{array}\right)j^{-s} $$ We have (using eg mathematica, though probably ...
1
vote
1answer
114 views

Condition Number and CFL Condition in Finite difference Methods [closed]

when applying a Finite Difference scheme for an IVP, two factors come to mind when considering stability: One factor would be the condition number of the approximation operator. The other factor ...
4
votes
3answers
236 views

Quadrature formula max accuracy

I'm looking for a maximum accuracy quadrature formula: $$ \int_{-1} ^{1} \sqrt{\frac {1-x}{1+x}} f(x)dx = A_1f(x_1)+A_2f(x_2)+R(f) $$ I don't know exactly if it's Trapezoidal rule which has the ...
3
votes
0answers
69 views

Deriving Milne's predictor of order four from extrapolation polynomial [closed]

I am trying to derive the following Milne's predictor formula of order four for the differential equation $\frac{dy}{dx}=f(x,y)$ from an extrapolation polynomial of degree four. $$y_{n+1} = y_{n-3}+\...
6
votes
0answers
218 views

An inequality which involves a sum of integrals

Please help me to prove $$ \sum\limits_{j=2}^n \frac{1}{j^\alpha (j-1)^\alpha} \int\limits_{j-1}^j \frac{dx}{x^{1-\alpha}(n-x)^\alpha} \leq \int\limits_0^1 \frac{dx}{x^{1-\alpha}(n-x)^\alpha},\quad \...
4
votes
2answers
75 views

Euler Schemes in Stochastic Differential Equations

So i am trying to understand what happens in Implicit (backward) and Explicit (forward) Euler in Stochastic Differential Equations I ll start with explicit. Say i have the following SDE known as ...
0
votes
0answers
24 views

Adaptive refinement of integral domain

In electromagnetics we need to calculate the radiated power which is defined as something like $P_r=\int_0^{2\pi}\int_0^{\pi}R(\theta,\phi)\sin{\theta}d{\theta}d\phi$ We already have $R(\theta,\phi)...
0
votes
1answer
95 views

Efficient computation of matrix exponential of trace zero matrix [closed]

I am looking for identities that may help with numerical computation of the matrix exponential ${\rm exp}(A)$ where ${\rm tr}(A)=0$. I am already aware of general-purpose algorithms for computing the ...
4
votes
2answers
276 views

Divergence of the Lagrange interpolation on the Chebyshev nodes

Faber theorem states that for every $\lbrace x_k^{(n)} \rbrace$ there exists a continuous function $f$ such that $\| f - L_n \|_{\infty} \not\rightarrow 0$, where $L_n$ is an interpolation polynomial ...
2
votes
3answers
598 views

Solving a system of algebraic equations

I am trying to find complex solutions with positive real part $\{t_j \;|\;{\rm Re}\;t_j>0, j = 1, 2, 3, \dots, n\}$ of the system of equations $$0 = 1 + \sum_j \left(t_j^{2l+1} + {t_j^*}^{2l+1}\...
5
votes
2answers
1k views

Algorithm for solving systems of linear Diophantine inequalities

So, I posted on StackOverflow looking for a reasonably fast algorithm to solve systems of linear Diophantine inequalities and was pointed to this article by Cheng-Zhi Gao and Yu-Lin Dong. The problem ...
1
vote
1answer
41 views

Subquadratic multiplication of probability mass functions (with log-convolution?)

We are currently looking for a fast, i.e. subquadratic, algorithm for the following equation: $z_m = \sum_{i,j :\, (i \cdot j) = m} x_i \cdot y_j$. That is, we are given two finite input vectors $x$ ...
1
vote
0answers
102 views

How to rotate a covariance matrix which contains quaternion elements? [closed]

I am implementing a paper which recovers full-3d body pose from images. It represents individual body parts as 7D vectors containing first the absolute 3D location [x y z] and then the unit ...
6
votes
2answers
864 views

Computational complexity of integration in two dimensions

I have an algorithm for solving a certain problem that requires that I compute two-dimensional integrals as a subroutine, and I'd like to make some kind of statement about its running time. Suppose $...
9
votes
1answer
249 views

How to compute $\sum_{x \in \mathbb{Z}^n} e^{-x^TMx}$ efficiently

Let $M$ be a real symmetric integer valued positive definite matrix with $\det(M) \geq 1$. I would like write code to compute $$S_M= \sum_{x \in \mathbb{Z}^n} e^{-x^TMx}.$$ One option is to simply ...
23
votes
9answers
3k views

What is… A Grossone?

Y. Sergeyev developed a positional system for representing infinite numbers using a basic unit called a "grossone", as well as what he calls an "infinity computer". The mathematical value of this ...
0
votes
0answers
51 views

Separable Least squares - is there a notion of conjugate directions?

I have a general question. Suppose I have the following to optimize $$\|Y-A(\mathbf{x})B(\mathbf{y})\|^2$$ where $Y$ is a vector, $A(\mathbf{x})$ is a matrix that depends on a vector $\mathbf{x}$ in a ...
4
votes
0answers
160 views

Efficiently calculate the trace of the product of two large but symmetric matrices, one of which is an inverse

Sorry about the long title. I need to calculate the trace of $M(M+D)^{-1}$, where $M$ is a dense symmetric matrix, and $D$ is a diagonal matrix. The main issue is the dimension could be large (usually ...
0
votes
0answers
27 views

Circulant Block Sparse Matrix Least Squares

I have what boils down to a least squares problem that I am trying to exploit structure in order to calculate efficiently. Consider a NxN circulant matrix A. Where the first row is [1,2,3,4,0,0,0,...,...
5
votes
1answer
245 views

Frozen coefficient method (von Neumann stability analysis)

Earlier it was considered that frozen coefficients method for Neumann stability analysis for finite difference scheme is more heuristic than rigorous. But I have read some information in a book by ...
4
votes
0answers
90 views

What does the Von Neumann's stability analysis tell us about non-linear finite difference equations?

I've asked this question on computation science stackexchange, but it did not receive any answers so I have decided to ask it here as well. I am reading a paper [1] where they solve the following non-...
46
votes
8answers
7k views

There must be a good introductory numerical analysis course out there!

Background As a numerical analyst, I've frequently taught the 'Introductory Numerical Analysis' class. Such courses are found in many major universities; the audience typically consists of reluctant ...
7
votes
1answer
78 views

Add a multiple of $I$ to a matrix to minimize its operator norm

Given $A\in\mathbb{C}^{n\times n}$, what is $s_* = \arg\min \|A-sI\|$? Here $\|A\|$ is the operator norm, $\|A\|=\rho(A^*A)^{1/2}$, and $I$ is the identity. The corresponding problem for the ...
12
votes
1answer
164 views

Interval arithmetic with different definitions of intervals

Interval arithmetic normally deals with intervals defined as $[a,b]$ with rules like $$[a,b]+[c,d]=[a+c,b+d]$$ I am interested in interval arithmetic with different interval definitions such as $$\{a\}...