This tag concerns computational problems central to mathematical and scientific computating. The scope includes algorithms, numerical analysis, optimization, and linear algebra, computational topology, computational geometry, symbolic methods, and inverse problems.

learn more… | top users | synonyms

0
votes
1answer
41 views

How is the status of a bigger number known while the smaller not?

In this wolfram mathworld article in the table below the status of $2059$ is known before the some smaller numbers, or they choose to aim the computation for that specific number?
7
votes
1answer
257 views

Why is Householder computationally more stable than modified Gram-Schmidt?

I'm having trouble nailing down why using Householder transformations yields a more stable/accurate result than the modified Gram-Schmidt method when computing the QR decomposition of a matrix. Can ...
0
votes
2answers
36 views

How can I find $x$ such that $ax \equiv 1 \pmod{bx+c}$, given $a,b,c$?

Everything I've read about modular arithmetic generally concerns doing things in some "mod m" world where "m" is some constant. But I'm perplexed how to tackle modular arithmetic problems where the ...
1
vote
0answers
403 views

Change MATLAB code from Lax-Wendroff to Leapfrog

I want to see how leapfrog would look using this code, but I'm having issues implementing it. I think my biggest problem is adding in the $ U_j^{n-1}$ term, I just don't get the logic. Here's what ...
1
vote
1answer
33 views

Pumping lemma contradiction

I have to prove that the language $A_{1}= \{\alpha \in \Sigma^{*}|c^{a}(\alpha)>c^{b}(\alpha) \}$ where $\Sigma=\{a,b\}$, where $c^{a}(a)$ means the number of $a$ in $\alpha$, and $c^{b}(\alpha)$ ...
2
votes
2answers
73 views

Very slow convergence of a particular series?

I've read that $$ \sum_{k=2}^{\infty} \frac{1}{k (\log k)^2} = 2.1097\ldots $$ However when I compute the partial sums it looks like a lot of terms are needed to even get the first decimals right. My ...
1
vote
1answer
32 views

Computational complexity of expanding a MacLaurin/Taylor Series

What methods exist to computationally determine the first $k$ coefficients of a function (possibly polynomial or rational polynomial function)? How do Mathematica/MatLab/Maple/etc. solve this ...
0
votes
0answers
24 views

Am I converting this Context Free Grammar correctly?

My homework problem is to convert this context free grammar into Chomsky Normal Form. ...
1
vote
2answers
91 views

summation of ceil and floor function

I need a closed solution or a faster algorithm for calculating $$ \sum_{k=1}^{n-1} \left\lceil \frac{n}{k}-1 \right\rceil $$ and $$ \sum_{k=1}^{n-1} \left\lfloor \frac{n}{k} \right\rfloor $$ where $ ...
0
votes
2answers
332 views

Google Code Jam's Cookie Clicker Program…

Today, the Google Code Jam's cookie clicker problem was something like this. Problem In this problem, you start with 0 cookies. You gain cookies at a rate of 2 cookies per second, by ...
3
votes
1answer
80 views

Factors of integers of the form $k^2-k+1$

Factorisation of arbitrary integers is of course a computationally hard problem. But what if the integers I'm interested in factorising are all of the form $k^2-k+1$ ? Is there some way to compute ...
1
vote
0answers
31 views

Generating N-dimensional points acording to given distribution

I searched here on Math.SE and haven't found anything that was exactly what I was looking for, so I'm posting it here. If there is anything, pardon my ignorance. I thought it was my first post here, ...
0
votes
0answers
25 views

finding the least non-zero of a multivariable polynomial

Let $P(x_1,x_2,...,x_m)$ be a homogeneous polynomial of degree n, with integers coefficients. How can you find the least* $a=(a_1,a_2,...,a_m)$, where $a_i$ are positive integers and $P(a)!\neq 0$? ...
1
vote
1answer
38 views

Please help with this Discrete fourier transform question

Consider the ODE $\frac {d^2u}{dx^2} + 2\pi\frac {du}{dx} + \frac 54\pi^2u = g(x)$ where g is a periodic fuction with period 1 given by $g(x) = e^{\pi x}$ , $ 0 \le x \lt 1$. It is desired to find ...
1
vote
1answer
29 views

Computational Maths - Normalised mantissa

What does overflow and underflow of an normalised mantissa mean?
1
vote
1answer
65 views

Max value - Mantissa calculation clarification?

I've been reading this article about floating point representation floating point representation is : Where mantissa is : All understood. But they also say : How did they get to ...
1
vote
1answer
68 views

Jacobi Iteration Question

I have a question that says use a relative tolerance of $10^{-3}$ and asks if the estimate errors are in line with the actual errors. What does relative tolerance mean and how do you work out ...
2
votes
1answer
95 views

Bisection Method Question, Multiple Roots

I understand how to do the bisection method and how to do it with a point of intersection. My question is should this not actually have multiple points of intersection? and if you're not given any ...
0
votes
1answer
35 views

Prove a language is Context Free

I am working on the following problem and I do make a little progress. Let me state the question first: Prove that the set of strings consisting of $a$'s and $b$'s with an equal number of $a$'s and ...
2
votes
0answers
38 views

Quantitatively comparing event trains of different lengths for Poissonness

I have a parameterized, effectively black box process that generates a series of events (simulated action potentials). Different parameter values often lead to different numbers of events. How can I ...
0
votes
1answer
30 views

Simple Error Question

I have a question which asks to find the absolute error and then asks if the actual error agrees with the theoretical error bound. Am I missing something or are absolute and actual error the same ...
3
votes
1answer
68 views

Computational Maths

I'm trying to revise for a test and these 2 questions I just don't really understand what I'm meant to do, any pointers would be good. Any help I'd be very grateful for.
1
vote
2answers
40 views

Knapsack variation NP-complete

I have C processors and $C$ items that have to be run on it. I can either run each item on a seperate processor and have a running time of $\sum_{i=1}^{c} c_i$, or divide the $C$ items into $k$ ...
0
votes
1answer
159 views

Computation Method to solving Homogeneous Fredholm Integral Equation of Second Kind with Symmetric Kernel

I am attempting to write a program that will be able to numerically solve a homogeneous Fredholm Integral Equation of Second Kind, with a Symmetric Kernel. I have been looking through textbooks and ...
3
votes
1answer
56 views

How do computers compute the expected value of an infinite distribution?

I was trying to compute: $$E[X] = \int^{\infty}_{-\infty} xP(x)dx$$ but it might be a distribution over a sample space that is infinite. How do computers actually deal with this in an efficient and ...
0
votes
1answer
71 views

Newton Cotes Rule Derivation

I have this question Derive an open two-point Newton-Cotes quadrature rule for the interval $[a,b]$. I need to find what the resulting weights and nodes are. What is the degree of the resulting rule? ...
1
vote
2answers
50 views

Computing an induced matrix norm

Assume I have a $n \times n$ matrix and a norm defined as $\|A\| = \max \limits_{x \not = 0}\frac{\|Ax\|}{\|x\|}$, where $\|x\| = \sqrt{\sum x_i^2}$. How can I compute this norm?
2
votes
1answer
82 views

No advantage to the closed form for Fibonacci numbers?

The closed forms for the Fibonacci sequence, such as: $$F_n=\frac{\varphi^n-\widehat\varphi^n}{\sqrt5}=\frac{\varphi^n}{\sqrt5}-\frac{\widehat\varphi^n}{\sqrt5}\;,$$ the Binet formula, do not seem ...
13
votes
2answers
212 views

$e$ popping up in topic I'm unfamiliar with

I programmed up a little algorithm that goes like this: Fix two positive, real numbers, call them $\alpha$ and $\beta$. Generate a new, random, real number, $x \in [0,1]$ Set $\alpha$ = ...
4
votes
1answer
317 views

“Opposite” of idempotent operation?

What is the adjective given to a mathematical operation/expression on a variable whose new value can only be described in terms of that variable's existing value? Sequential operation? Example: i = ...
0
votes
3answers
68 views

How would I convert from frequency back to percent?

I'm working on a web application that uses an oscillator. It has a parameter that goes from 0 to 100 percent. I translate that percent into hertz using this equation: $$ \text{frequency} = ...
0
votes
0answers
33 views

Is there a way to expand Re(Li(a^z)) in series?

I'm searching a way to expand $ f(z) = Re(Li(a^z)), a \in R, z \in C $ in series. The computer-friendly, quickly convergent series is a huge plus. For being 'computer-friendly' I mean a relatively ...
0
votes
2answers
106 views

Existing Algorithm / Code to calculate exact values of the Riemann Zeta function at even natural numbers?

I wanted to know if there's any existing algorithm to compute exact values of the Riemann Zeta function at even natural numbers? For example, it should compute $\zeta(4)$ as exactly $\frac{\pi^4}{90}$ ...
0
votes
0answers
35 views

Properties of linear systems involving band matrices

Let $N$ be a positive integer, $A$ be a square matrix of size $2N+1$, and $x$ and $b$ be vectors of size $2N+1$. All the elements of $b$ are nonzero except for the middle element, $b_{N+1}$. Also, $A$ ...
1
vote
1answer
66 views

mortage with monthly payment - mathematical modeling

$Question:$ Suppose that $x_n$ is the amount owed on a mortgage after n years, $\$m$ is the monthly repayment and $r$ is the annual percentage interest rate charged on the amount of the mortgage ...
0
votes
0answers
20 views

Echo State Network learning Mackey-Glass function, but how?

I got this example of a minimal Echo State Network (ESN) which I analyse while trying to understand Echo State Networks. Unfortunately I have some problems understanding why this really works. It all ...
2
votes
1answer
231 views

How To Generate Random Points on the Positive Side of a Plane in 3-D

Edit: The question can also be interpreted as: How to generate random coplanar points in a cube? Here is what I am struggling with: I have a cube, whose origin is $(0,0,0)$ and one edge length ...
2
votes
1answer
48 views

Find regular expression for a binary sequence dividable by 3

I am trying to find a short regular expression that matches to all binary sequences that are dividable by 3. This is homework. It would be great if I could only get some hints before the final ...
1
vote
0answers
28 views

Find allowed error of an argument regarding the allowed error of a function.

To what precision can $x$ be obtained with logarithmic table (with $5$ digit table) if $x$ lies between $300$ and $400$? Any ideas?
3
votes
4answers
158 views

Computing a large exp(x) in a numerically robust way.

I'm trying to compute $\lfloor e^x \rfloor$, where x is a 64-bit integer. The problem is that the result of the computation may be close to 2^64. In this range, 64-bit floating point numbers will be ...
2
votes
1answer
52 views

The “computability” of fundamental physical constants

I would like to ask if any of the fundamental physical quantities like the speed of light or plancks constant (all measured according to a common standard of of units) can be classified as computable ...
0
votes
1answer
79 views

Discretize an ellipsoid given its semi-major axes and orientation

An ellipsoid centered at the origin can be defined by the solutions to $$ \mathbf{x}^\text{T} A \mathbf{x} = 1 $$ where $A$ is symmetric and positive-definite. The eigenvectors of $A$ define the ...
2
votes
1answer
45 views

Generating Eulerian digraphs/isographs

I would like to be able to quickly generate (all) non-isomorphic isographs (that is, digraphs where each node has the same indegree and outdegree - also called "balanced networks" in the distributed ...
0
votes
2answers
69 views

logarithm and exponent computation performance

Using glibc on a x86 processor, which takes more CPU time? $a\ log\ b$ or $b^a$? For which values of $a$ is one faster than the other? Optional: Does the base used matter? See also: What algorithm ...
0
votes
1answer
252 views

Calculating eigenvectors and eigenvalues of a 2x2 complex matrix

I've previously asked elsewhere, http://stackoverflow.com/questions/21118820/non-trivial-eigenvectors-of-a-22-matrix-in-code, how to calculate the eigenvectors and eigenvalues of a 2x2 matrix in a ...
1
vote
1answer
54 views

Is it possible to reduce a lambda expression to it's smallest equivalent form?

In the Untyped Lambda Calculus, is it possible to reduce any arbitrary expression to it's smallest equivalent form? (defined as an expression with the smallest number of lambda terms) If so, is there ...
2
votes
2answers
178 views

Galois group command for Magma online calculator?

I need to test if a family of 7th deg and 13 deg equations are solvable. I'm new to Magma, so my apologies, but what would I type in, http://magma.maths.usyd.edu.au/calc/ to determine the Galois ...
3
votes
0answers
69 views

Computing the decomposition of a representation of $S_n$

I have an explicitly defined representation of the symmetric group that I would like to decompose into irreducibles. How to do this most easily? The best approach I have so far is as follows: Find a ...
3
votes
0answers
50 views

Algorithm for primary decomposition of ideals in a power series ring over a field

Let $K$ be a field such that there exists an algorithm for factoring a polynomial over $K$ into the product of irreducible polynomials. For example, the field of rational numbers $\mathbb{Q}$ is such ...
5
votes
3answers
274 views

FFT with powers of 3

Classic Fast Fourier Transfrom (FFT) works fine, when $n$ is power of 2. How to generalize FFT procedure when $n$ is power of 3? Is it possible to easily modify the algorithm and preserve its ...