Research in Scientific Computing in Undergraduate Education

001. Potential Research Projects: Fall 2011 – Spring 2012

Numerical Analysis

Research Project 1: Numerical differentiation and integration

Adviser: Professor Yanlai Chen
yanlai.chen@umassd.edu

Despite the abundance of analytical methods for differentiating and  integrating functions, most differentiations and integrations  either cannot be done in this way or the result may be of little practical use.

Numerical differentiation formulas can be used to estimate the derivatives of a function given its values at certain number of points. Numerical integration techniques are needed when the function to be integrated may be known only at a set of distinct points. 

The aim of this project is to work on a sequence of differentiation and integration rules through implementations in MATLAB and calculus-based theoretical analysis. Situation permitting, highly-oscillating functions, such as solutions of the Airy equation,  and sparse grids will be explored.
x
References:
Arieh Iserles, “On the numerical analysis of rapid oscillation“, Centre de Recherches Mathematiques, CRM Proceedings and Lecture Notes
x

Research Project 2: Solving nonlinear equations using Newton’s method

Adviser: Professor Yanlai Chen
yanlai.chen@umassd.edu

Realistic physical processes have to be observed and phenomenologically studied in order to obtain detailed knowledge of the inherent structure of the system. A systematic study usually starts with the design of a mathematical model, involving an equation or a set of equations. These equations could be nonlinear which, unfortunately, makes them harder to solve.

Moreover, these equations must be solved as efficiently as possible for simulations to be acceptable in terms of computational cost. 
Newton’s method for solving nonlinear equations was first published three hundred years ago but is essentially still the method of choice today. 

This project will involve studying some variants of Newton’s method and comparing their performance on a sequence of Matlab test examples.
x

Computational finance/economics

Adviser: Professor Yanlai Chen
yanlai.chen@umassd.edu
x
The project would be based around the text Numerical Methods in Finance and Economics by P. Brandimarte, 2006, John Wiley & Sons.
x
By understanding, experimenting with and extending the MATLAB codes described in the book, the student will learn about some modern numerical methods and their use in financial engineering and economics.
x
Research projects in computational finance might, for example, involve looking at variants of the Black-Scholes model for derivative pricing.
x
Other areas to explore may include option pricing by Binomial Lattices, Monte Carlo Methods, and Finite Difference Methods for the Black-Scholes equation.
x

Boundary layer problems for differential equations

Research Project: Boundary layer resolving spectral method

Adviser: Professor Yanlai Chen & Professor Alfa Heryudono
yanlai.chen@umassd.edu ; aheryudono@umassd.edu

x

Consider the differential equation

x

\epsilon u'' + p(x) u' + q(x) = f

x

on the interval (-1, 1) with \epsilon << 1.

x

There has been substantial progress in the development of numerical methods for the solution of such problems in the last few decades.

 x

A small region near the ends of the interval  where the slope of the solution curve is changing most rapidly is called the boundary layer.

x

A collocation method is a method for the numerical solution of  differential equations is based on choosing a collection of candidate solutions, usually polynomials up to a certain degree, and a number of points in the domain (called collocation points), and to select that solution which satisfies the given equation at the collocation points.

x

In this project, you will study one particular collocation approach that can resolve the boundary layers efficiently. The corresponding two-dimensional boundary layers and model-reduction techniques will be examined.
x
Reference:
x

Computational Number Theory

Adviser: Professor Gary Davis

gdavis@umassd.edu

An excellent – and free – reference for background to research projects in this area is Victor Shoup’s book: A Computational Introduction to Number Theory and Algebra. Carl Pomerance has an excellent, but more advanced, review of big research problems in computational number theory.

Research project 1: Searching for Catalan pseudoprimes

The Catalan numbers arise in a wide variety of counting problems.  The nth Catalan number Cn turns out to be \frac{1}{n+1}\begin{pmatrix} 2n \\n \end{pmatrix}, where \begin{pmatrix}2n \\n \end{pmatrix} is the middle binomial number: the number of ways of choosing n objects from 2n.

In 2008, Christian Aebi and Grant Cairns discovered a connection between Catalan numbers and prime numbers:

Theorem: If p is an odd prime then (-1)(p-1)/2 C(p-1)/2 = 2 (mod p)

[Christian Aebi &Grant Cairns, Catalan Numbers, Primes and Twin Primes, Elemente der Mathematik 63 (2008), no. 4, 153–164]

This says that for prime numbers p\geq 3 the remainder when (-1)(p-1)/2 C(p-1)/2 is divided by p is 2.

This test allows us to tell which numbers p are not prime numbers. However, Aebi & Cairns theorem does not say that if (-1)(p-1)/2 C(p-1)/2 = 2 (mod p) then p is prime. Indeed there are counterexamples to this: p = 5907 = 3\times11\times179.

Numbers p >2 for which p is not prime but (-1)(p-1)/2 C(p-1)/2 = 2 (mod p) are called Catalan pseudoprimes by Aebi & Cairns.

So 5907 is a Catalan pseudoprime.

Are there others?

Yes: 1194649 = 10932 and 12327121 = 35112 are both Catalan pseudoprimes.

These are the only Catalan pseudoprimes Aebi & Cairns could find.

Through a computational search they showed that there are no Catalan pseudoprimes less than 1010 of the form pq, where p, q are distinct primes.

The aim of this project is to search for Catalan pseudoprimes, or to show that there are no more.

Reference: Catalan pseudoprimes

Research project 2: Computational evidence for an inequality It is widely believed, but still not known, if the fractional part of (\frac{3}{2})^n, namely (\frac{3}{2})^n-Floor[(\frac{3}{2})^n], satisfies the inequality: (\frac{3}{2})^n-Floor[(\frac{3}{2})^n] \leq 1-(\frac{3}{4})^n for all n\geq 1

If this inequality is true then a famous problem of number theory – Waring’s problem – is known to be true.

The inequality  seems innocent enough, yet no-one to date has been able to prove it is true.

The aim of this project is to computationally quantify how close the inequality above comes to failing, and, if possible, to find a counterexample.

Reference: Some stubborn problems associated with the number 3/2

Research project 3: Zeroes in the digits of powers of 2

It is suspected that 86 is the last n for which 2^n does not have a (decimal) digit equal to 0.

Showing that 2^n always has a digit equal to 0 for n\geq 87 seems to be beyond the tools of present day mathematics.

However, we can statistically investigate a stronger question: how many zeroes are there in the digits of 2^n?

A simple model is that 2^n should have about \frac{1}{10}^{\textrm{th}} of its digits equal to 0, at least for large n.

The number of digits of 2^n is about \log_{10}(2^n) for large n, so we suspect that 2^n should have about n\log_{10}(2)/10\approx 0.030103n of its digits equal to 0 for large n.

Computations indicate that the number of zeroes in  2^n is n\log_{10}(2)/10 +\epsilon_n where the “error” \epsilon_n is fairly well behaved.

The aim of this project is to get tight bounds on the “error” \epsilon_n and to potentially prove the estimate for the number of zeroes in 2^n.

Reference: How many zeros are there in 2^n?

Discrete Dynamical Systems

Research Project 1: Random Fibonacci-type sequences

Adviser: Professor Alfa Heryudono

aheryudono@umassd.edu

The Fibonacci sequencef_1,f_2,f_3,\ldots is defined recursively by: f_1=1, f_2=1, f_n=f_{n-1}+f_{n-2} \textrm{ for } n\geq3

It is known – and not hard to show – that the terms f_n increase exponentially at the rate of \Phi^n where \Phi=\frac{1}{2}(1+\sqrt{5})\approx 1.61803398.

If we modify the recursive definition of the Fibonacci sequence to: f_1=1, f_2=1, f_n=\pm f_{n-1}\pm f_{n-2} \textrm{ for } n\geq3 where each \pm sign is chosen independently and randomly at each iteration with equal probabilities for + and for -, then these new sequences (there are many, dependent on how the + and – signs pan out) also increase exponentially  in size – i.e. \vert f_n\vert increases exponentially – at a rate \sigma^n where \sigma \approx 1.13198824, with probability 1 (i.e. “almost all” of them do so).

References:

Now consider the random sequence x_{n+1} = x_n \pm \beta x_{n-1} where the sign + or − is chosen independently with equal probability at random at every iteration.

It turns out that these sequences decay exponentially as n\to \infty with probability 1 for 0<\beta <\beta^* and growexponentially for \beta> \beta^* where  \beta^* \approx 0.70258 is known as the Embree-Trefethen constant. Reference:

This project is concerned with modifying recurrence formula by choosing + and – signs, as above, according to different probability distributions, and studying  the Lyapunov constant \sigma = \lim_{n \to \infty} \vert x_n\vert^{1/n} which measures the growth of solutions \vert x_n\vert.

Random Fibonacci-type  sequences are important in many fields such as dynamical systems, statistical mechanics, spectral theory, and condensed matter physics. We will pick up some applications based on students’ interests.

Further references:

Research Proejct 2: Integer values of recurrences

Adviser: To be determined

Victor Moll writes:

“The recurrence x[n] = (n + x[n - 1])/(1 - nx[n - 1]) comes from a simple finite sum of values of the arctangent function. Starting at x[0] = 0 you will see that x[n] \textrm{ is an integer for } n \leq 4. We have conjectured that this never happens again.

The paper “Arithmetical properties of a sequence arising from an arctangent sum” (see below) contains some dynamical systems that needs to be explored.” The aim of his project is to explore this conjecture computationally.

In particular, what is the behavior of the sequence of fractional parts frac[x[n]]:=x[n]-\textrm{Floor}[x[n]] of the x[n] defined in the Amdeberhan et al(2007) article?

A plot of x[n] \textrm{ versus } n \textrm{ for } 0\leq n \leq 50 shows two values of n for which frac[x[n]] is small, namely n=16 \textrm{ and } n=37

However, a check reveals that frac[x[16]]= \frac{3154072}{87995911}\approx 0.0358434 and frac[x[37]]=\frac{107145788085395791884}{62134508741384128482689} \approx 0.00172442 .

A plot of x[n] \textrm{ for } 0 \leq n \leq 10000 reveals spots, increasingly rare, where frac[x[n]]\approx 0

References & readings

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: