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
14 views

What are good techniques for creating a DFA state diagram given a set of accepted/rejected strings?

I am in a Discrete Structures class and my teacher went to MIT so he is pretty big on proving his intellect to the class and getting an average of about 60% for his test questions. Right now we are ...
4
votes
1answer
52 views

What mathematics topics pertain more towards applied mathematics?

I'm entering my second year of undergrad (majoring in mathematics), and I've found that I am really bad at Linear Algebra, but very good at Calculus and Differential Equations. I'm hoping to venture ...
1
vote
2answers
37 views

How can you expand the adjoint of a matrix into a polynomial with matrix coefficients?

This book contains an algorithm which claims that a matrix $sI - A$, where $A$ is some $n \times n $ square matrix and $s$ a variable can be expanded into $$adj(sI - A) = K_0 s^{n-1} + K_1 s^{n-2} ...
0
votes
0answers
20 views

Quantify difference between regularity and irregularity

I am solving an equation numerically on a 1D-domain using the finite-element method. I am solving it using two different domains, one regular and one irregular. Naturally, the solution varies slightly ...
0
votes
1answer
21 views

Stability of (floating point) computed variance

Homework Question from Accuracy and Stability of Numerical Algorithms, 2nd Edition, by Nicholas J. Higham, page 33: So every time we store an number and do a operation, we introduce an error bounded ...
0
votes
0answers
23 views

How can I modify this simple code to include the pressure term? (1-D Navier Stokes)

I have a mathematical model that involves a cylindrical container that is being modeled with a one dimensional simplification as the system is isotropic with respect to the z-axis. As part of the ...
2
votes
0answers
49 views

I have a finite permutation group and access to a computer algebra system, how can I recognize the structure of the group?

I have a fixed permutation group $G$, and cannot tell which finite group it really is in a "human readable" way. I also have GAP. Is there a step by step computation to give me the structure of this ...
3
votes
1answer
58 views

Finite difference method works for $\frac{\partial u}{\partial t} = \frac{du}{dz}$ but not for $\frac{\partial u}{\partial t} = - \frac{du}{dz}$?

I am using the method of lines with forward differences to solve the transport equation $$\frac{\partial u}{\partial t} = \frac{du}{dz}$$ with initial condition $u(z, 0) = z$ and boundary condition ...
2
votes
0answers
11 views

How to compute Generalized Group Inverse?

Given a transition matrix $P \in \mathbb{R}^{n \times n}$, i.e. $\sum_j P_{ij} = 1$ and $P_{ij} \geq 0$ for all $i,j$. One can show that there exists a unique group inverse $B$ of $A:= I - P$ which ...
-2
votes
0answers
24 views

How to find coordinates of points on a 2D surface embedded in 3D space

kindly assist with this problem. Given an equilateral triangle in 2D plane (see figure 1) with origin (0,0) at point B, the coordinates of points A and C can be calculated as A(acos60,asin60) and ...
1
vote
0answers
14 views

Minimum vertex cover of vertex disjoint odd holes and antiholes

I am interested in knowing whether the minimum vertex cover of a graph that can be written as the union of vertex-disjoint odd holes and odd antiholes can be found exactly, in polynomial time. I could ...
0
votes
0answers
24 views

How to use the false-position method

I have two equations; 1) $$ 0 = 7x+13$$ and 2) $$0 = 2x-13$$ Why can I use the false position/secant method in the first equation, but not in the second? Further, how does one go about using this ...
0
votes
0answers
35 views

Multiplications in determinant of an $n \times n$ matrix?

Assuming we use Gaussian Elimination/LU decomp, is there a general formula to describe the number of multiplications involved in finding the determinant of an $N \times N$ matrix? Find the ...
3
votes
2answers
72 views

An efficient way to find anagrams

Consider a set of words where you want to divide the set into subsets of words, where all members of each subset are anagrams (same letters, different arrangement). You can do this computationally in ...
0
votes
2answers
47 views

Clarification about the concept of number

I am reading a book called Numerical Notation: A Comparative History (by Stephen Chrisomalis). The first chapter (Introduction), second and third paragraph go like this: If you look up from this ...
1
vote
0answers
26 views

How can we calculate the tensor product of Lagrange basis polynomials?

Given data points $(x_i,y_i)$, the Lagrange basis polynomials are $$\mathcal l_j(x):=\sum_{i\ne j}\frac{x-x_i}{x_j-x_i}\;.$$ I'm reading a text targeting Smolyak's algorithm. In this text, they use ...
1
vote
2answers
52 views

Maple not able to calculate Bernstein polynomial

Hope you can help me on this one. Please look at this simple Maple code: Obviously $B(1)=g(1)=4 \neq 0$. Why is Maple not able to compute this right? Am I doing something wrong? Kind regards PS: ...
0
votes
1answer
21 views

Finding the bounds for a truncation error

I have two series, $S$ and $T$ which approximate $\pi$ such that $$S_n = 4 \sum_{i=1}^n \cfrac{-1^{i+1}}{2i-1}$$ and $$T_n = \Big(12 \sum_{i=1}^n \cfrac{-1^{1+i}}{k^2} \Big) ^{\frac{1}{2}}$$ It is ...
1
vote
0answers
13 views

What does “empirical error” mean in this context?

I recently sat an exam for computational mathematics. The question asked for us to: "Write the empirical error in $\mathcal{O}(n^{-p})$ where $p$ is some integer" We were given a series $$S = 4(1 - ...
4
votes
0answers
75 views

On a unique(?) binomial property of $3003$

Given the triangular number, $$T_k = \frac{k(k+1)}{2}$$ and remembering that, $$\binom{n}{m}=\binom{n}{n-m}$$ Excluding $a_0=1$, we then have the six-fold (at least) equalities, $$\begin{aligned} ...
0
votes
0answers
33 views

How to calculate $det(X^T X)$ efficiently, update one column of X each time

$X_{1} = (A, b)$, where $X_{1}$ is a $n\times p$ matrix, $A$ is a $n\times (p-1)$ and $b$ is $n\times1$. First calculate $\det(X_{1}^T X_{1})$, then update $b$ with $c$, st. $X_{2} = (A, c)$ and ...
2
votes
3answers
56 views

What is the value of this function?

Consider the three-variable function defined at the following way for all natural numbers $n,x,y$ : $f(0,x,y) = x+y $ $f(n,x,0) = x$ $f(n,x,y) = f(n-1, $ $ $ $f(n,x,y-1) , $ $ $ $f(n,x,y-1)+y ) $. ...
2
votes
2answers
51 views

(Fast way to) Get a combination given its position in (reverse-)lexicographic order

This question is the inverse of the Fast way to get a position of combination (without repetitions). Given all $\left(\!\!\binom{n}{k}\!\!\right)$ combinations without repetitions (in either ...
0
votes
0answers
48 views

Need to solve for an angle, do I need to use numerical methods??

I need to run a simulation on MATLAB where I need to solve two equations for two unknowns. The equations look something like this, $$x_{comp} = G\cdot \cos^2 b \cdot \cos(a+b).$$ $$z_{comp} = ...
1
vote
1answer
65 views

Expected Utility Method and a Repeated Game Solution

I am trying to replicate Bruce B. de Mesquita's (BDM) results on political game theory for prediction. Based on where actors stand on issues, their capabilities, salience, BDM's method attempts to ...
3
votes
3answers
131 views

Fast way to get a position of combination (without repetitions)

This question has an inverse: (Fast way to) Get a combination given its position in (reverse-)lexicographic order What would be the most efficient way to ...
0
votes
1answer
52 views

Constructive Induction to derive and prove the formula for a geometric sequence

$\sum_{i=1}^nr^i = a \cdot (b^n) + c$ Base Case: n=1, this holds Inductive Hypothesis: Assume for $n = k$, $k \ge 1$ that $\sum_{i=1}^k r^i = a * (b^k) + c$. Inductive Step: Prove for $n = k+1$ ...
0
votes
0answers
30 views

In bipartite directed graph, how to efficiently find nontrivial edge values such that for each node, sum of edge values is zero?

Suppose I have a set of sources U and a set of sinks V and a set of directed edges E going from elements of U to elements of V. I want to find a vector z of size |E| (each value of z is assigned to ...
8
votes
1answer
92 views

Are the unit partial quotients of $\pi, \log(2), \zeta(3) $ and other constants $all$ governed by $H=0.415\dots$?

Khinchin showed that given the simple continued fraction of a real number, $$r = a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1} {\ddots}}}$$ then it is almost always true that the partial quotients $a_i$ ...
0
votes
1answer
33 views

Seeking the Recommendation on Complexity Theory books

S.E advisers, I am a rising college junior in US with a major in mathematics and an aspiring applied mathematician in the fields of theoretical computing. I just recently got a research project on ...
0
votes
0answers
17 views

How can I measure the dispersion of a discrete time system?

I have a discrete time system: x[n+1]=A*x[n]+B[n], with B[n] as an excitation signal. How can I measure the dispersion of this system? I guess this is related to some property of A, which depicts the ...
2
votes
2answers
90 views

Verify input is the sum of other numbers

I have a relationship: 4000k + 2500j + 400g = n, k >= 0, 0 <= j <= k, 0 <= g <= j I have to, given n, verify ...
2
votes
1answer
72 views

How do computers generate primes so quickly?

From what I understand, when a computer encrypts a file using an encryption standard like RSA, one of the steps is to generate two large primes, and multiply them together. I have created RSA keys on ...
6
votes
5answers
266 views

Computing as many digits as possible of $\sqrt{2}$ with a pen and a paper in 5 minutes

You have to compute as many digits as possible of $\sqrt{2}$ with a pen and a paper (an eraser if you're lucky...) in 5 minutes. What will you do? What is your justification for doing it? The ...
0
votes
0answers
23 views

Unknown variable in formula - binomial coefficient? [duplicate]

I'm currently researching a filter and don't quite understand one of the equations used there, since it contains a variable I don't know how to calculate: $$(1)\,\,a^{m, k}_s = \frac{c^{k, ...
0
votes
0answers
22 views

hyperoperation sequence with non-integer values of n

This probably has a very simple answer of some sort, but I'm not a mathematician. For the hyperoperation sequence: $$G(n,a,b)$$ ...there are obvious defined values for positive integer values of $n$ ...
0
votes
0answers
29 views

deconvolution of exp($x^2$)

I would like to know whether we can get the function of type exp($x^2$) by convoluting any functions. That is which function convolution gives exp($x^2$). Thanks in advance
1
vote
1answer
27 views

computing a fixed interest rate

I've been struggling for hours now with understanding a Topcoder problem, Autoloan , but i cannot grasp the way of computing it from a mathematical point of view. The excerpt goes as follows: A ...
0
votes
0answers
19 views

Analytical expressions for the orthogonalization of a specific set of vectors

I would like to know whether analytical or closed-form expressions could be obtained for the orthogonalization of a set of vectors in the following setting. Let $x_t$ be a vector indexed as a time ...
0
votes
1answer
17 views

Calculate height for rows of rectangles within a given width

I have an array of rectangles, all of the same height, but with different widths. Imagine they are on a single line with a uniform gap between them as shown below... |XXX| |X| |XXXXX| |XXX| ...
1
vote
2answers
63 views

Can car traffic be managed by mathematical formula? [closed]

How car traffic is managed? Is it managed by mathematical algorithm? Or by human(operator)? If it's by operator, can it be managed mathematically? Or is it by physics? By what theories/formula? ...
2
votes
1answer
28 views

Approximate recursively defined error in fixed point iteration

Problem: With an initial guess of $x_0$, the fixed point iteration is given by $$x_{k+1} = e^{-x_k}, \mbox{ for } k=0,1,2,...$$ If $x^*$ is the exact solution, then the approximation error is $$e_n = ...
1
vote
2answers
77 views

Is there any sort algorithm quicker than Quicksort given a random array of integers?

How can we proof (mathematically) that any complexity of sorting algorithm that sorts a random array of integers is no better than $O(n\log n)$?
1
vote
0answers
17 views

Is there a way to delineate the parameter of highest influence in a system of differential equations?

So I have a system of nonlinear ordinary differential equations dependent on parameters. These equations can traditionally be solved numerically with robust methods and the solution is well defined. ...
0
votes
0answers
7 views

State-of-Art library or a method for paralell matrix inversion?

Do you have reference to a computer library or a paper regarding a state-of-art method to obtain inverse of a matrix in parallel? Thanks, Mojo.
8
votes
0answers
76 views

Generalizing Bellard's “exotic” formula for $\pi$ to $m=11$

Bellard's "exotic" pi formula has the form, $$a\pi+b = \sum_{n=1}^\infty \dfrac{P(n)}{{\displaystyle \binom{mn}{2n}2^{n-1}}}$$ where $a,b,m$ are integers and he uses $m=7$. However, it seems there ...
0
votes
0answers
16 views

FFT differential equations

Given a generical differential equation what is the procedure to solve it using fft command. Can anyone explain me how to do it? For example: $$\frac{d^2y}{dt^2}+10\cdot \frac{d\:y}{dt}=-5\cdot ...
0
votes
0answers
11 views

How to solve the Helmholtz equation in a triangular region?

Suppose we take the Dirichlet boundary condition, namely the function must vanish on the boundary of the triangle. How about a general n-polygon?
-1
votes
1answer
29 views

What is transpose multiplier and forward multiplier?

For linear system X = A*s, we define the forward and transpose multiplies Af and At as follows: Af = @(s) A*s; At = @(s) A'*s; I want to know what is forward ...
1
vote
0answers
42 views

Simplifying the Generalized Eigenvalue Problem

Let $\Sigma_1$, $\Sigma_2$ be symmetric positive-definite real $n\times n$ matrices. We want to solve the generalized eigenvalue problem $$ \Sigma_1V=\Lambda\Sigma_2V, $$ where $\Lambda$ is the ...