Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-12-22
2004-12-14
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06832233
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an apparatus and method for computing multiple integral, and a recording medium. More particularly, to an apparatus and method for high speed multidimensional integration of given integrand functions which are defined over a multi-dimensional unbounded domain, and a recording medium in which a program for realizing the apparatus and the method for computing multiple integral.
2. Description of the Related Art
Problems relating to computation of multiple integral on a multi-dimensional unbounded domain appear in various technical fields such as risk evaluation in financial derivative calculation, evaluating interference noises in multiple-user communication systems such as CDMA (Code Division Multiple Access), and the like.
In case of numerical integration on 1- or 2-dimensional domain, the domain (interval) can be divided into fine subdomains, and an approximated integral can be obtained as an average of represented values of an integrand function on each subdomain.
If the integration domain is in higher dimension, however, the domain must be divided into the great number of subdomains. The number of the subdomains must exponentially increase with respect to the dimensionality of the integration domain to maintain the commutative efficiency. This problem is called “curse of dimensionality”.
Monte Carlo method has been proposed as one of solutions for such the problems. Monte Carlo method usually employs pseudo-random numbers (including quasi random numbers such as low-discrepancy sequences) on the finite interval which should be uniformed as possible.
In a case where integral must be defined in an unbounded domain such as infinite domain [−∞, +∞], however, it is impossible to normalize uniformed random numbers on a bounded domain after converting the uniformed random numbers on the finite interval into uniformed random numbers on the unbounded domain by a linear transformation. In this case, a useful non-linear change of variables is required.
The inverse function method was established by J. von Neumann and S. Ulam in 1947. According to the method, it is able to generate random numbers in accordance with an arbitrary density function from uniformed random numbers on the finite interval. In that year, they carried out computer simulation for tracing fission neutrons, and it was successful. Since the method utilizes an inverse function, it is called inverse function method. More precisely, the inverse function &eegr;
−1
(X) is used for generating uniformed
&eegr;(
X
)=∫
c
&rgr;(
x
)
dx
(
C={u|−∞≦u≦X
})
It has been turned out that random numbers having non-uniformed distribution on a bounded domain are available, as chaos theory have been developed recently. Chaotic dynamical mapping systems are getting more significant matters for random number generation.
Recurrence formula is usually applicable to the random number generation. In this case, a rational map is often used as the recurrence formula which generates ideally chaotic sequences. The rational map there is a result of the addition theorem of an elliptic function (including a trigonometric function). The random number generation by such the method has the following advantages.
(1) Non-cyclical random number sequence generation by which the numbers are proven to be chaotic (without some exceptions).
(2) According to sensitivity to initial conditions of chaos, completely different random number sequences are available just by slightly changing the seeds (the initial values to be applied to the recurrence formula).
(3) Known analytic function acts as the density function expressing random number distribution.
Known maps which bring the above advantages are: an Ulam-von Neumann map, a cubic map, a quintic map, and the like.
Ulam-von Neumann Map: f(x)=4x (1−x)
Cubic Map: f(x)=x (3−4x)
2
Quintic Map: f(x)=x(5−20x+16x
2
)
2
Regardless of the different maps above, &rgr;(x)=1/(&pgr;(x(1−x))
1/2
) represents a density function expressing distribution of a random number sequence x[i] (i≧0) (x[0], x[1], x[2], . . . ) which results from the following recurrence formula:
x[i
+1
]=f
(
x[i
]) (i≧0)
Japanese Unexamined Patent Application KOKAI Publication No. H10-283344 by Umeno et al. discloses a technique for generating random numbers on a bounded domain with using those maps, and embodiments where the technique is applied to Monte Carlo numerical integration. The following references disclose theoretical backgrounds for the above described application.
S. M. Ulam and J. von Neumann, Bull. Math. Soc. 53 (1947) p1120.
R. L. Adler and T. J. Rivlin, Proc. Am. Math. Soc. 15 (1964) p794.
K. Umeno, Method of constructing exactly solvable chaos, Phys. Rev. E (1997) vol. 55, pp. 5280-5284.
The above conventional technique, however, includes the following problems.
Monte Carlo numerical integration on unbounded domain requires random numbers which are distributed in the unbounded domain in accordance with a density function given by a known analytic function. Therefore, obtained uniform random numbers must be converted into the random numbers distributed in the unbounded domain. To obtain random numbers distributed in accordance with a desired density function with using the aforementioned von Neuman's inverse function method, an integral function of the density function must be obtained first, and then, an inverse function of the integral function must be obtained.
However, it is almost impossible to analytically integrate the density function. Moreover, approximation and calculation time accompanying to numerical calculation must be considered seriously when obtaining the inverse function of the integral function resulting from the density function. Since the Monte Carlo method requires the great number of random numbers, it is a hard task to calculate the integral with using the Monte Carlo method by the inverse function method.
The numerical integration in a unbounded domain is also required for solving the Black-Scholes equation for stock option pricing based on the data of stock prices. If integration on a unbounded domain is useful for solving the Black-Scholes equation.
It has been turned out, however, that density function expressing actual distribution of stock price fluctuation shows power-law behavior (R. N. Mantegna and H. E. Stanley, Nature, vol. 376, pp. 46-49, 1995). Integral of such the density function showing the power-law behavior can not be expressed by elementary functions. Therefore, it is very difficult to solve the stock price fluctuation with using the Monte Carlo integration on an unbounded domain based on known uniform random numbers.
Such the problems also appear in evaluation of communication traffic or interference noises in CDMA showing power-law behavior in transmission time distribution or in background noise distribution respectively.
The application of process to efficient computation of multiple integral on a unbounded domain has recently been attracting attention in industry fields.
It is an object of the present invention to provide an apparatus and a method for computing multiple integral, and a recording medium storing a program for realizing the above, which are suitable for high speed numerical integration of integrands which are defined over a multi-dimensional unbounded domain.
SUMMARY OF THE INVENTION
The invention for achieving the above object will now be disclosed in accordance with the principal of the present invention.
An apparatus for computing multiple integral according to a first aspect of the present invention computes multiple integral represented by a multidimensional integrand function A to be integrated with using a vector map f. The vector map f has an unbounded support, and converts an m (m≧1)-dimensional vector having a real number components into an m-dimensiona
Communications Research Laboratory, Ministry of Posts and Teleco
Luce Forward Hamilton & Scripps LLP
Ngo Chuong Dinh
LandOfFree
Apparatus and method for computing multiple integral, and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for computing multiple integral, and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for computing multiple integral, and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3329534