The Research On Polylog And Weak Tractability Of Multivariate Problems

In many subjects,such as physics,chemistry,computational sciences,quantum me-chanics,finance,economics,etc..we often encounter the problems of numerical approx-imation defined in d dimensional multivariate functional spaces,where d may be large,in the hundreds or in the thousands,even larger.When the mumber of variables d is very large,we usually use the either linear functionals(linear information)or function values(standard information)as the information to construct algorithm to approximate the problem within a threshold error ε.The complexity of the algorithm for approximat-ing the multivariate numerical problem,denoted by C(n,ε,d),has been one of the main research directions in computational mathematics in recent years.The minimal number of information that algorithms needed to approximate the multivariate problem is called the complexity of the information,denoted by n(ε,d).Obviously,information complexity is a lower bound of computational complexity,especially for many linear problems,the information complexity is proportional to the computational complexity,so the research of computational complexity focuses on the complexity of information.The tractability of multivariate problems mainly studies how the n(ε,d)depends onε and d through the analysis.Traditionally the complexity of multivariate problems was studied while considering the number of variables d to be arbitrary but fixed.This ignores the dependence of the complexity on d,yet the complexity may depend on d exponential-ly.So the study of multivariate problems requires a significant amount of new research.In 1994,Polish mathematician Wozniakowski proposed many new concepts and theories of tractability of multivariate problems,for example,intractability,strong tractability,weak tractability,polynomial tractability,weak and quasi-polynomial tractability,polylog tractability.Many scholars have studied and obtained a lot of nwe results in recent years.In this thesis,we will mainly make a further study on polylog and weak tractability of multivariate problems in the average case setting.The main work of the thesis includes the following chapters:In the first chapter,we briefly introduce the research background and development history of information based on complexity and tractability,then we gave some basic concepts,notations and results.In the second chapter,we mainly discuss the tractability of multivariate problems in average case setting,and give necessary and sufficient conditions for the polylog tractability and(s,lnk)-weak tractability of the multivariate problem.Then we discuss the weighted approximation problem and prove that the lnk-weak tractability are equivalent in the classes of linear information and standard information.In the third chapter,we will discuss tensor product problems in the average case setting.We give some basic concepts,then provide necessary and sufficient conditions for the(s,t)-weak tractability of the multivariate problem.Finally,we prove the tensor product problems are neither(1,ln1)-weakly tractable nor polylog tractable.The last chapter summarizes the previous chapters,give some ideas for future research in the average case setting and a few of temporary unresolved problems.