I. Introduction
A major characteristic of the American options is that they can be exercised prior to the maturity date. Pricing of American options is known to be a difficult problem especially when the number of underlying assets is large. Methods for pricing of an American option include Monte Carlo simulation, regression approach (See Tsitsiklis and Van Roy (1999) and Longstaff and Schwartz (2001)) and stochastic mesh method (See Broadie and Glasserman (1997),Avramidis and Hyden (1999), Avramidis and Matzinger (2004), Liu G and Hong L.J (2008)).