Practical Applications of Randomness

at Hiroshima University, 2007 March 26

Date:	2007 March 26 (Mon.)
Place:	Hiroshima University, Faculty of Science Building B, B707
	1-3-1, Kagamiyama, Higashi Hiroshima, JAPAN

Program

Speakers:

Pierre L'Ecuyer 教授　(モントリオール大学)、　伏見正則 教授　（南山大学）

Talks:

Pierre L'Ecuyer 教授
　（Departement d'Informatique et de Recherche Operationnelle, Universite de Montreal, Montreal, CANADA)

講演題目：A Practical View of Randomized Quasi-Monte Carlo

講演概要：

Quasi-Monte Carlo (QMC) methods are numerical techniques for estimating large-dimensional integrals, usually over the unit hypercube. They can be applied, at least in principle, to any stochastic simulation whose aim is to estimate a mathematical expectation. This covers a wide range of applications. Practical error bounds are hard to obtain with QMC but randomized quasi- Monte Carlo (RQMC) permits one to compute an unbiased estimator of the integral, together with a confidence interval. RQMC can in fact be viewed as a variance-reduction technique.

In this talk, we review some key ideas of RQMC methods and provide concrete examples of their application to simulate systems modeled as Markov chains. We also present a new RQMC method, called array-RQMC, recently introduced to simulate Markov chains over a large number of steps. The array-RQMC method is joint work with Christian Universite de Savoie) and Bruno Tuffin (IRISA).

伏見正則 教授　（南山大学数理情報学部）

講演題目：Parallel pseudo-random number generation with special reference to built-in self-test of VLSI
講演概要：

Parallel computations are often used for large scale Monte Carlo simulations, in which we want to have independent (or at least uncorrelated) streams of (pseudo-)random numbers. Several algorithms for generating independent streams of random numbers have been proposed so far. We briefly review some of them in the first part of this talk.

Independent streams of random numbers are also necessary to test VLSI chips for malfunctions. Since the number of gates of a VLSI chip is more than a million, it is impossible to test a chip by exhaustively checking all the states that the chip can assume, and some mechanism of random sampling of the states is necessary. It is natural to include a testing mechanism into a chip to shorten the time required for test procedures. When we include a random number generator into a VLSI chip, it is desirable to make the area that the generator assumes as compact as possible. Cellular automata are preferable to linear feedback shift registers in this respect. We discuss a method of designing good celullar automata for generating independent substreams of pseudo-random test patterns. Some computational results will be reported.

共催：
　日本オペレーションズ・リサーチ学会中国・四国支部
The Operations Research Society of Japan - Chugoku-Shikoku Chapter
　広島大学ミニワークショップ実行委員会
Hiroshima University Mini Workshop Comittee (Hiroshima Univ.- Dept. of Math: Makoto Matsumoto)
（広島大学大学院理学研究科 松本 眞）

協賛：
　JSPS (Japan Society for Promotion of Science)
　Core-to-Core Program 18005; Grant-in-Aid for Scientific Research 18654021