Numerical algorithms for problems in analysis and algebra, scientific computation

learn more… | top users | synonyms

112
votes
2answers
11k views

What are the shapes of rational functions?

I would like to understand and compute the shapes of rational functions, that is, holomorphic maps of the Riemann sphere to itself, or equivalently, ratios of two polynomials, up to Moebius ...
34
votes
7answers
4k views

What is the time complexity of computing sin(x) to t bits of precision?

Short version of the question: Presumably, it's poly$(t)$. But what polynomial, and could you provide a reference? Long version of the question: I'm sort of surprised to be asking this, because ...
7
votes
4answers
1k views

Is there a name for the matrix equation A X B + B X A + C X C = D?

I happen to be working on a problem that reduces to solving the following equation: $$\mathbf{A X B} + \mathbf{B X A} + \mathbf{C X C} = \mathbf{D}$$ where A through D are known matrices ( A, B, D ...
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 ...
6
votes
2answers
3k views

Computational complexity of calculating the nth root of a real number

Several sources state that the computational or time complexity of square rooting is the same as that of multiplication (or division). See for example: Jean-Michel Muller, "Elementary Functions: ...
10
votes
1answer
217 views

Confusion with practically implementing rational approximations

Writing a program visualizing Ford circles I've encountered a seemingly purely programmatic puzzle but then gradually realized there are some mathematical aspects of it which I don't understand. Let ...
3
votes
1answer
226 views

Are piecewise linear functions dense in $W^{1,\infty}$?

Are piecewise linear functions dense in $W^{1,\infty}$ ?
2
votes
0answers
159 views

Are there workable numerical approaches for the pentagon equation?

Warning: this post is the "numerical" analog of Are there workable algebraic geometry approaches for the pentagon equation? I've replaced "algebraic geometry" by "numerical" in its content, ...
9
votes
1answer
267 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 ...
9
votes
3answers
555 views

Degree necessary of a polynomial?

Given $-1<a<b<0$, I want to find a polynomial $f(x)\in\Bbb R[x]$ such that $f(x)\in[a,b]$ at every $x\in[b^2,a^2]$ and $f(0)=0$. What is minimum degree that is needed and maximum degree that ...
6
votes
3answers
943 views

Dependence of error on mesh for Riemann sums

Suppose $f$ is continuous on $[a,b]$ with $I = \int_a^b f(x)\: dx$, and for every $\epsilon > 0$ let $\delta(\epsilon)$ be the largest $\delta > 0$ such that every Riemann sum arising from a ...
5
votes
0answers
108 views

Error of midpoint method for differentiable functions

Is it the case that for every differentiable function $f$ on $[0,1]$ (with finite one-sided derivatives at the endpoints), the midpoint method of estimating $\int_0^1 f(x) \: dx$ has error $o(1/n)$? ...
3
votes
0answers
948 views

Eigenvalue Problems with Linear Constraints

The motivation for this problem comes from trying to develop a simple way to decompose domains into non-overlapping subdomains to solve for the eigenvalues of some differential operator. The idea is ...
2
votes
1answer
120 views

cohomology algebra of submanifold in euclidean space

If we write a manifold or CW-complex $X$ as a subset of $\mathbb{R}^n$, in expression of coordinates, for example, \begin{multline} F(S^2,k+1)=\{(x_1,x_2,x_3,\cdots, x_{3k+1},x_{3k+2},x_{3k+3})\in\...
0
votes
1answer
166 views

Regular Perturbation Series soln to eqn

I want to find the a 3 term perturbation soln of (i) $(1+x)^3 = ex$ where $e\ll1$ Direct substitution of the regular perturbation series $x = x_0 + ex_1 + e^2x_2$ into (i) does not work I ...
11
votes
2answers
410 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,...
6
votes
2answers
126 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 ...
4
votes
1answer
87 views

The link and equivalence between variant definition of computation model and computational complexity over reals

To unify the numerical computation and classic computability theory, or to pave a foundation for the numerical computation, mathematicians present variant computation model and computational ...
3
votes
1answer
158 views

Approximate the square root of (1-X) efficiently through (nested) products

Currently, I encountered a problem of approximating the following series: $$ (I-X)^{-\frac{1}{2}}=I+\frac{1}{2}X+\frac{1\cdot3}{2\cdot4}X^{2}+\frac{1\cdot3\cdot5}{2\cdot4\cdot6}X^{3}+\ldots $$ where ...
3
votes
1answer
221 views

Error of midpoint method for functions that are not twice-differentiable

All of the bounds I've seen for the error of the midpoint method of integration are expressed in terms of the second derivative of the function. What bounds are available when the function is not ...
2
votes
2answers
2k views

Finding the formula for Bezier curve ratios (hull/point : point/baseline)

Given a cubic Bezier curve defined by points $p_1$, $p_2$, $p_3$, and $p_4$, a point $B$ on that curve at some $t$ value (where $0 \leq t \leq 1$), a point $A$ on the line $(p_2 - p_3)$ at distance ...
2
votes
1answer
92 views

Is is preferable to use a difference formula of higher order of accuracy for spatial derivatives to solve this IVP problem ?

I want to numerically integrate the equation $\partial_t u= a(t) \partial_xu+b\partial_{xxx}u+c$ to get $u(t)$. Is is preferable to use a difference formula of higher order of accuracy for spatial ...
0
votes
0answers
220 views

Solving a parabolic PDE with boundary conditions given over ranges

How can one solve a Parabolic PDE (like the wave or diffusion equations) if the boundary conditions were given over ranges? Here is an example: How to solve the equation $u_{xx}+u_{yy}-\alpha^{2}u_{t}...