共查询到20条相似文献,搜索用时 62 毫秒
1.
Given a set X of sequences over a finite alphabet, we investigate the following three quantities.
- (i)
- The feasible predictability of X is the highest success ratio that a polynomial-time randomized predictor can achieve on all sequences in X.
- (ii)
- The deterministic feasible predictability of X is the highest success ratio that a polynomial-time deterministic predictor can achieve on all sequences in X.
- (iii)
- The feasible dimension of X is the polynomial-time effectivization of the classical Hausdorff dimension (“fractal dimension”) of X.
2.
3.
This work presents a new version of a software package for the study of chaotic flows, maps and fractals [1]. The codes were written using Scilab, a software package for numerical computations providing a powerful open computing environment for engineering and scientific applications. It was found that Scilab provides various functions for ordinary differential equation solving, Fast Fourier Transform, autocorrelation, and excellent 2D and 3D graphical capabilities. The chaotic behaviors of the nonlinear dynamics systems were analyzed using phase-space maps, autocorrelation functions, power spectra, Lyapunov exponents and Kolmogorov-Sinai entropy. Various well-known examples are implemented, with the capability of the users inserting their own ODE or iterative equations.
New version program summary
Program title: Chaos v2.0Catalogue identifier: AEAP_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEAP_v2_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 1275No. of bytes in distributed program, including test data, etc.: 7135Distribution format: tar.gzProgramming language: Scilab 5.1.1. Scilab 5.1.1 should be installed before running the program. Information about the installation can be found at http://wiki.scilab.org/howto/install/windows.Computer: PC-compatible running Scilab on MS Windows or LinuxOperating system: Windows XP, LinuxRAM: below 150 MegabytesClassification: 6.2Catalogue identifier of previous version: AEAP_v1_0Journal reference of previous version: Comput. Phys. Comm. 178 (2008) 788Does the new version supersede the previous version?: YesNature of problem: Any physical model containing linear or nonlinear ordinary differential equations (ODE).Solution method:- 1.
- Numerical solving of ordinary differential equations for the study of chaotic flows. The chaotic behavior of the nonlinear dynamical system is analyzed using Poincare sections, phase-space maps, autocorrelation functions, power spectra, Lyapunov exponents and Kolmogorov-Sinai entropies.
- 2.
- Numerical solving of iterative equations for the study of maps and fractals.
- 1.
- A new use case concerning coupled predator-prey models has been added [3].
- 2.
- Three new use cases concerning fractals (Sierpinsky gasket, Barnsley's Fern and Tree) have been added [3].
- 3.
- The graphical user interface (GUI) of the program has been reconstructed to include the new use cases.
- 4.
- The program has been updated to use Scilab 5.1.1 with the new graphical capabilities.
- •
- interface.sce - the graphical user interface (GUI) that permits the choice of a routine as follows
- •
- 1.sci - Lorenz dynamical system
- •
- 2.sci - Chua dynamical system
- •
- 3.sci - Rosler dynamical system
- •
- 4.sci - Henon map
- •
- 5.sci - Lyapunov exponents for Lorenz dynamical system
- •
- 6.sci - Lyapunov exponent for the logistic map
- •
- 7.sci - Shannon entropy for the logistic map
- •
- 8.sci - Coupled predator-prey model
- •
- 1f.sci - Sierpinsky gasket
- •
- 2f.sci - Barnsley's Fern
- •
- 3f.sci - Barnsley's Tree
- [1]
- C.C. Bordeianu, C. Besliu, Al. Jipa, D. Felea, I. V. Grossu, Comput. Phys. Comm. 178 (2008) 788.
- [2]
- S. Campbell, J.P. Chancelier, R. Nikoukhah, Modeling and Simulation in Scilab/Scicos, Springer, 2006.
- [3]
- R.H. Landau, M.J. Paez, C.C. Bordeianu, A Survey of Computational Physics, Introductory Computational Science, Princeton University Press, 2008.
4.
micrOMEGAs2.0.7 is a code which calculates the relic density of a stable massive particle in an arbitrary model. The underlying assumption is that there is a conservation law like R-parity in supersymmetry which guarantees the stability of the lightest odd particle. The new physics model must be incorporated in the notation of CalcHEP, a package for the automatic generation of squared matrix elements. Once this is done, all annihilation and coannihilation channels are included automatically in any model. Cross-sections at v=0, relevant for indirect detection of dark matter, are also computed automatically. The package includes three sample models: the minimal supersymmetric standard model (MSSM), the MSSM with complex phases and the NMSSM. Extension to other models, including non supersymmetric models, is described.
Program summary
Title of program:micrOMEGAs2.0.7Catalogue identifier:ADQR_v2_1Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADQR_v2_1.htmlProgram obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandLicensing provisions:Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.:216 529No. of bytes in distributed program, including test data, etc.:1 848 816Distribution format:tar.gzProgramming language used:C and FortranComputer:PC, Alpha, Mac, SunOperating system:UNIX (Linux, OSF1, SunOS, Darwin, Cygwin)RAM:17 MB depending on the number of processes requiredClassification:1.9, 11.6Catalogue identifier of previous version:ADQR_v2_0Journal version of previous version:Comput. Phys. Comm. 176 (2007) 367Does the new version supersede the previous version?:YesNature of problem:Calculation of the relic density of the lightest stable particle in a generic new model of particle physics.Solution method:In numerically solving the evolution equation for the density of dark matter, relativistic formulae for the thermal average are used. All tree-level processes for annihilation and coannihilation of new particles in the model are included. The cross-sections for all processes are calculated exactly with CalcHEP after definition of a model file. Higher-order QCD corrections to Higgs couplings to quark pairs are included.Reasons for new version:The main changes in this new version consist, on the one hand, in improvements of the user interface and treatment of error codes when using spectrum calculators in the MSSM and, on the other hand, on a completely revised code for the calculation of the relic density in the NMSSM based on the code NMSSMTools1.0.2 for the computation of the spectrum.Summary of revisions:- •
- The version of CalcHEP was updated to CalcHEP 2.4.
- •
- The procedure for shared library generation has been improved. Now the libraries are recalculated each time the model is modified.
- •
- The default value for the top quark mass has been set to 171.4 GeV.
- •
- The deltaMb correction is now included in the B,t,H-vertex and is always included for other Higgs vertices.
- •
- In case of a fatal error in an RGE program, micrOMEGAs now continues operation while issuing a warning that the given point is not valid. This is important when running scans over parameter space. However this means that the standard ˆC command that could be used to cancel a job now only cancels the RGE program. To cancel a job, use “kill -9 -N” where N is the micrOMEGAs process id, all child processes launched by micrOMEGAs will be killed at once.
- •
- Following the last SLHA2 release, we use key=26 item of EXTPAR block for the pole mass of the CP-odd Higgs so that micrOMEGAs can now use SoftSUSY for spectrum calculation with EWSB input. The Isajet interface was corrected too, so the user has to recompile the isajet_slha executable. For SuSpect we still support an old “wrong” interface where key=24 is used for the mass of the CP-odd Higgs.
- •
- In the non-universal SUGRA model, we set the value of M0 (M1/2,A0) to the value of the largest subset of equal parameters among scalar masses (gaugino masses, trilinear couplings). In the previous version these parameters were set arbitrarily to be equal to MH2, MG2 and At respectively. The spectrum calculators need an input value for M0,M1/2 and A0 for initialisation purposes.
- •
- We have removed bugs in micrOMEGAs-Isajet interface in case of non-universal SUGRA.
- •
- $(FFLAGS) is added to compilation instruction of suspect.exe. It was omitted in version 2.0.
- •
- The treatment of errors in reading of the LesHouches accord file is improved. Now, if the SPINFO block is absent in the SLHA output it is considered as a fatal error.
- •
- Instructions for calculation of Δρ, μ(g−2), Br(b→sγ) and Br(Bs→μ+μ−) constraints are included in EWSB sample main programs omg.c/omg.cpp/omg.F.
- •
- We have corrected the name of the library for neutralino-neutralino annihilation in our sample files MSSM/cs br.*.
- •
- The NMSSM has been completely revised. Now it is based on NMSSMTools_1.0.2.
- •
- The deltaMb corrections in the NMSSM are included in the Higgs potential.
- •
- We have included in our package the MSSM with CP violation. Our implementation was described in Phys. Rev. D 73 (2006) 115007. It is based on the CPSUPERH package published in Comput. Phys. Comm. 156 (2004) 283.
5.
6.
For computer simulations on heavy ion beam (HIB) irradiation onto a target with an arbitrary shape and structure in heavy ion fusion (HIF), the code OK2 was developed and presented in Computer Physics Communications 161 (2004). Code OK3 is an upgrade of OK2 including an important capability of wobbling beam illumination. The wobbling beam introduces a unique possibility for a smooth mechanism of inertial fusion target implosion, so that sufficient fusion energy is released to construct a fusion reactor in future.
New version program summary
Program title: OK3Catalogue identifier: ADST_v3_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADST_v3_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 221 517No. of bytes in distributed program, including test data, etc.: 2 471 015Distribution format: tar.gzProgramming language: C++Computer: PC (Pentium 4, 1 GHz or more recommended)Operating system: Windows or UNIXRAM: 2048 MBytesClassification: 19.7Catalogue identifier of previous version: ADST_v2_0Journal reference of previous version: Comput. Phys. Comm. 161 (2004) 143Does the new version supersede the previous version?: YesNature of problem: In heavy ion fusion (HIF), ion cancer therapy, material processing, etc., a precise beam energy deposition is essentially important [1]. Codes OK1 and OK2 have been developed to simulate the heavy ion beam energy deposition in three-dimensional arbitrary shaped targets [2, 3]. Wobbling beam illumination is important to smooth the beam energy deposition nonuniformity in HIF, so that a uniform target implosion is realized and a sufficient fusion output energy is released.Solution method: OK3 code works on the base of OK1 and OK2 [2, 3]. The code simulates a multi-beam illumination on a target with arbitrary shape and structure, including beam wobbling function.Reasons for new version: The code OK3 is based on OK2 [3] and uses the same algorithm with some improvements, the most important one is the beam wobbling function.Summary of revisions:- 1.
- In the code OK3, beams are subdivided on many bunches. The displacement of each bunch center from the initial beam direction is calculated.
- 2.
- Code OK3 allows the beamlet number to vary from bunch to bunch. That reduces the calculation error especially in case of very complicated mesh structure with big internal holes.
- 3.
- The target temperature rises during the time of energy deposition.
- 4.
- Some procedures are improved to perform faster.
- 5.
- The energy conservation is checked up on each step of calculation process and corrected if necessary.
- 1.
- Procedure BeamCenterRot( ) rotates the beam axis around the impinging direction of each beam.
- 2.
- Procedure BeamletRot( ) rotates the beamlet axes that belong to each beam.
- 3.
- Procedure Rotation( ) sets the coordinates of rotated beams and beamlets in chamber and pellet systems.
- 4.
- Procedure BeamletOut( ) calculates the lost energy of ions that have not impinged on the target.
- 5.
- Procedure TargetT( ) sets the temperature of the target layer of energy deposition during the irradiation process.
- 6.
- Procedure ECL( ) checks up the energy conservation law at each step of the energy deposition process.
- 7.
- Procedure ECLt( ) performs the final check up of the energy conservation law at the end of deposition process.
- 1.
- Procedure InitBeam( ): This procedure initializes the beam radius and coefficients A1, A2, A3, A4 and A5 for Gauss distributed beams [2]. It is enlarged in OK3 and can set beams with radii from 1 to 20 mm.
- 2.
- Procedure kBunch( ) is modified to allow beamlet number variation from bunch to bunch during the deposition.
- 3.
- Procedure ijkSp( ) and procedure Hole( ) are modified to perform faster.
- 4.
- Procedure Espl( ) and procedure ChechE( ) are modified to increase the calculation accuracy.
- 5.
- Procedure SD( ) calculates the total relative root-mean-square (RMS) deviation and the total relative peak-to-valley (PTV) deviation in energy deposition non-uniformity. This procedure is not included in code OK2 because of its limited applications (for spherical targets only). It is taken from code OK1 and modified to perform with code OK3.
- [1]
- A.I. Ogoyski, et al., Heavy ion beam irradiation non-uniformity in inertial fusion, Phys. Lett. A 315 (2003) 372-377.
- [2]
- A.I. Ogoyski, et al., Code OK1 - Simulation of multi-beam irradiation on a spherical target in heavy ion fusion, Comput. Phys. Comm. 157 (2004) 160-172.
- [3]
- A.I. Ogoyski, et al., Code OK2 - A simulation code of ion-beam illumination on an arbitrary shape and structure target, Comput. Phys. Comm. 161 (2004) 143-150.
7.
S. Nath 《Computer Physics Communications》2009,180(11):2392-2393
8.
Consider the “Number in Hand” multiparty communication complexity model, where k players holding inputs x1,…,xk∈{0,1}n communicate to compute the value f(x1,…,xk) of a function f known to all of them. The main lower bound technique for the communication complexity of such problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem.In this paper, we study the power of partition arguments. Our two main results are very different in nature:
- (i)
- For randomized communication complexity, we show that partition arguments may yield bounds that are exponentially far from the true communication complexity. Specifically, we prove that there exists a 3-argument function f whose communication complexity is Ω(n), while partition arguments can only yield an Ω(logn) lower bound. The same holds for nondeterministiccommunication complexity.
- (ii)
- For deterministic communication complexity, we prove that finding significant gaps between the true communication complexity and the best lower bound that can be obtained via partition arguments, would imply progress on a generalized version of the “log-rank conjecture” in communication complexity. We also observe that, in the case of computing relations (search problems), very large gaps do exist.
9.
In this paper we report on LCG Monte-Carlo Data Base (MCDB) and software which has been developed to operate MCDB. The main purpose of the LCG MCDB project is to provide a storage and documentation system for sophisticated event samples simulated for the LHC Collaborations by experts. In many cases, the modern Monte-Carlo simulation of physical processes requires expert knowledge in Monte-Carlo generators or significant amount of CPU time to produce the events. MCDB is a knowledgebase mainly dedicated to accumulate simulated events of this type. The main motivation behind LCG MCDB is to make the sophisticated MC event samples available for various physical groups. All the data from MCDB is accessible in several convenient ways. LCG MCDB is being developed within the CERN LCG Application Area Simulation project.
Program summary
Program title: LCG Monte-Carlo Data BaseCatalogue identifier: ADZX_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADZX_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: GNU General Public LicenceNo. of lines in distributed program, including test data, etc.: 30 129No. of bytes in distributed program, including test data, etc.: 216 943Distribution format: tar.gzProgramming language: PerlComputer: CPU: Intel Pentium 4, RAM: 1 Gb, HDD: 100 GbOperating system: Scientific Linux CERN 3/4RAM: 1 073 741 824 bytes (1 Gb)Classification: 9External routines:- •
- perl >= 5.8.5;
- •
- Perl modules
- ○
- DBD-mysql >= 2.9004,
- ○
- File::Basename,
- ○
- GD::SecurityImage,
- ○
- GD::SecurityImage::AC,
- ○
- Linux::Statistics,
- ○
- XML::LibXML > 1.6,
- ○
- XML::SAX,
- ○
- XML::NamespaceSupport;
- •
- Apache HTTP Server >= 2.0.59;
- •
- mod auth external >= 2.2.9;
- •
- edg-utils-system RPM package;
- •
- gd >= 2.0.28;
- •
- rpm package CASTOR-client >= 2.1.2-4;
- •
- arc-server (optional)
10.
O. Chuluunbaatar A.A. Gusev A.G. Abrashkevich 《Computer Physics Communications》2009,180(8):1358-1375
A FORTRAN 77 program is presented for calculating with the given accuracy eigenvalues, eigenfunctions and their first derivatives with respect to the parameter of the parametric self-adjoined Sturm-Liouville problem with the parametric third type boundary conditions on the finite interval. The program calculates also potential matrix elements - integrals of the eigenfunctions multiplied by their first derivatives with respect to the parameter. Eigenvalues and matrix elements computed by the ODPEVP program can be used for solving the bound state and multi-channel scattering problems for a system of the coupled second-order ordinary differential equations with the help of the KANTBP programs [O. Chuluunbaatar, A.A. Gusev, A.G. Abrashkevich, A. Amaya-Tapia, M.S. Kaschiev, S.Y. Larsen, S.I. Vinitsky, Comput. Phys. Commun. 177 (2007) 649-675; O. Chuluunbaatar, A.A. Gusev, S.I. Vinitsky, A.G. Abrashkevich, Comput. Phys. Commun. 179 (2008) 685-693]. As a test desk, the program is applied to the calculation of the potential matrix elements for an integrable 2D-model of three identical particles on a line with pair zero-range potentials, a 3D-model of a hydrogen atom in a homogeneous magnetic field and a hydrogen atom on a three-dimensional sphere.
Program summary
Program title: ODPEVPCatalogue identifier: AEDV_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEDV_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC license, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 3001No. of bytes in distributed program, including test data, etc.: 24 195Distribution format: tar.gzProgramming language: FORTRAN 77Computer: Intel Xeon EM64T, Alpha 21264A, AMD Athlon MP, Pentium IV Xeon, Opteron 248, Intel Pentium IVOperating system: OC Linux, Unix AIX 5.3, SunOS 5.8, Solaris, Windows XPRAM: depends on- 1.
- the number and order of finite elements;
- 2.
- the number of points; and
- 3.
- the number of eigenfunctions required.
- 1.
- the number and order of finite elements;
- 2.
- the number of points; and
- 3.
- the number of eigenfunctions required.
- 1.
- the number and order of finite elements;
- 2.
- the number of points on interval [zmin,zmax]; and
- 3.
- the number of eigenfunctions required.
- [1]
- O. Chuluunbaatar, A.A. Gusev, A.G. Abrashkevich, A. Amaya-Tapia, M.S. Kaschiev, S.Y. Larsen, S.I. Vinitsky, Comput. Phys. Comm. 177 (2007) 649-675
- [2]
- O. Chuluunbaatar, A.A. Gusev, S.I. Vinitsky, A.G. Abrashkevich, Comput. Phys. Comm. 179 (2008) 685-693.
- [3]
- W.H. Press, S.A. Teukolsky, W.T. Vetterling, B.P. Flannery, Numerical Recipes: The Art of Scientific Computing, Cambridge University Press, Cambridge, 1986.
- [4]
- O. Chuluunbaatar, A.A. Gusev, S.I. Vinitsky, V.L. Derbov, L.A. Melnikov, V.V. Serov, Phys. Rev. A 77 (2008) 034702-1-4.
- [5]
- E.M. Kazaryan, A.A. Kostanyan, H.A. Sarkisyan, Physica E 28 (2005) 423-430.
- [6]
- Yu.N. Demkov, J.D. Meyer, Eur. Phys. J. B 42 (2004) 361-365.
- [7]
- P.M. Krassovitskiy, N.Zh. Takibaev, Bull. Russian Acad. Sci. Phys. 70 (2006) 815-818.
- [8]
- V.S. Melezhik, J.I. Kim, P. Schmelcher, Phys. Rev. A 76 (2007) 053611-1-15.
- [9]
- F.M. Pen'kov, Phys. Rev. A 62 (2000) 044701-1-4.
- [10]
- M. Born, X. Huang, Dynamical Theory of Crystal Lattices, The Clarendon Press, Oxford, England, 1954.
- [11]
- L.V. Kantorovich, V.I. Krylov, Approximate Methods of Higher Analysis, Wiley, New York, 1964.
- [12]
- U. Fano, Colloq. Int. C.N.R.S. 273 (1977) 127;
- A.F. Starace, G.L. Webster, Phys. Rev. A 19 (1979) 1629-1640.
- [13]
- C.V. Clark, K.T. Lu, A.F. Starace, in: H.G. Beyer, H. Kleinpoppen (eds.), Progress in Atomic Spectroscopy, Part C, Plenum, New York, 1984, pp. 247-320.
- [14]
- O. Chuluunbaatar, A.A. Gusev, V.L. Derbov, M.S. Kaschiev, L.A. Melnikov, V.V. Serov, S.I. Vinitsky, J. Phys. A 40 (2007) 11485-11524.
- [15]
- A.G. Abrashkevich, D.G. Abrashkevich, M.S. Kaschiev, I.V. Puzynin, Comput. Phys. Comm. 85 (1995) 40-64.
- [16]
- K.J. Bathe, Finite Element Procedures in Engineering Analysis, Englewood Cliffs, Prentice-Hall, New York, 1982.
- [17]
- O. Chuluunbaatar, A.A. Gusev, M.S. Kaschiev, V.A. Kaschieva, A. Amaya-Tapia, S.Y. Larsen, S.I. Vinitsky, J. Phys. B 39 (2006) 243-269.
- [18]
- Yu.A. Kuperin, P.B. Kurasov, Yu.B. Melnikov, S.P. Merkuriev, Ann. Phys. 205 (1991) 330-361.
- [19]
- O. Chuluunbaatar, A.A. Gusev, V.P. Gerdt, V.A. Rostovtsev, S.I. Vinitsky, A.G. Abrashkevich, M.S. Kaschiev, V.V. Serov, Comput. Phys. Comm. 178 (2008) 301-330.
- [20]
- A.G. Abrashkevich, M.S. Kaschiev, S.I. Vinitsky, J. Comp. Phys. 163 (2000) 328-348.
11.
12.
This work presents a new version of a Visual Basic 6.0 application for estimating the fractal dimension of images (Grossu et al., 2009 [1]). The earlier version was limited to bi-dimensional sets of points, stored in bitmap files. The application was extended for working also with comma separated values files and three-dimensional images.
New version program summary
Program title: Fractal Analysis v02Catalogue identifier: AEEG_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEEG_v2_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 9999No. of bytes in distributed program, including test data, etc.: 4 366 783Distribution format: tar.gzProgramming language: MS Visual Basic 6.0Computer: PCOperating system: MS Windows 98 or laterRAM: 30 MClassification: 14Catalogue identifier of previous version: AEEG_v1_0Journal reference of previous version: Comput. Phys. Comm. 180 (2009) 1999Does the new version supersede the previous version?: YesNature of problem: Estimating the fractal dimension of 2D and 3D images.Solution method: Optimized implementation of the box-counting algorithm.Reasons for new version:- 1.
- The previous version was limited to bitmap image files. The new application was extended in order to work with objects stored in comma separated values (csv) files. The main advantages are:
- a)
- Easier integration with other applications (csv is a widely used, simple text file format);
- b)
- Less resources consumed and improved performance (only the information of interest, the “black points”, are stored);
- c)
- Higher resolution (the points coordinates are loaded into Visual Basic double variables [2]);
- d)
- Possibility of storing three-dimensional objects (e.g. the 3D Sierpinski gasket).
- 2.
- In this version the optimized box-counting algorithm [1] was extended to the three-dimensional case.
- 1.
- The application interface was changed from SDI (single document interface) to MDI (multi-document interface).
- 2.
- One form was added in order to provide a graphical user interface for the new functionalities (fractal analysis of 2D and 3D images stored in csv files).
- [1] I.V. Grossu, C. Besliu, M.V. Rusu, Al. Jipa, C.C. Bordeianu, D. Felea, Comput. Phys. Comm. 180 (2009) 1999-2001.
- [2] F. Balena, Programming Microsoft Visual Basic 6.0, Microsoft Press, US, 1999.
13.
Robert Elsässer 《Theoretical computer science》2011,412(24):2623-2641
We study the cover time of multiple random walks on undirected graphs G=(V,E). We consider k parallel, independent random walks that start from the same vertex. The speed-up is defined as the ratio of the cover time of a single random walk to the cover time of these k random walks. Recently, Alon et al. (2008) [5] derived several upper bounds on the cover time, which imply a speed-up of Ω(k) for several graphs; however, for many of them, k has to be bounded by O(logn). They also conjectured that, for any 1?k?n, the speed-up is at most O(k) on any graph. We prove the following main results:
- •
- We present a new lower bound on the speed-up that depends on the mixing time. It gives a speed-up of Ω(k) on many graphs, even if k is as large as n.
- •
- We prove that the speed-up is O(klogn) on any graph. For a large class of graphs we can also improve this bound to O(k), matching the conjecture of Alon et al.
- •
- We determine the order of the speed-up for any value of 1?k?n on hypercubes, random graphs and degree restricted expanders. For d-dimensional tori with d>2, our bounds are tight up to logarithmic factors.
- •
- Our findings also reveal a surprisingly sharp threshold behaviour for certain graphs, e.g., the d-dimensional torus with d>2 and hypercubes: there is a value T such that the speed-up is approximately min{T,k} for any 1?k?n.
14.
We give a lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. We use this lower bound to show that the treewidth of a d-dimensional hypercube is at least ⌊3·2d/(2(d+4))⌋−1. The currently known upper bound is . We generalize this result to Hamming graphs. We also observe that every graph G on n vertices, with maximum degree Δ
- (1)
- contains an induced cycle (chordless cycle) of length at least 1+logΔ(μn/8) (provided G is not acyclic),
- (2)
- has a clique minor Kh for some ,
15.
Venkatesh Raman 《Information Processing Letters》2007,104(2):65-72
We give improved parameterized algorithms for two “edge” problems MAXCUT and MAXDAG, where the solution sought is a subset of edges. MAXCUT of a graph is a maximum set of edges forming a bipartite subgraph of the given graph. On the other hand, MAXDAG of a directed graph is a set of arcs of maximum size such that the graph induced on these arcs is acyclic. Our algorithms are obtained through new kernelization and efficient exact algorithms for the optimization versions of the problems. More precisely our results include:
- (i)
- a kernel with at most αk vertices and βk edges for MAXCUT. Here 0<α?1 and 1<β?2. Values of α and β depends on the number of vertices and the edges in the graph;
- (ii)
- a kernel with at most 4k/3 vertices and 2k edges for MAXDAG;
- (iii)
- an O∗(k1.2418) parameterized algorithm for MAXCUT in undirected graphs. This improves the O∗(k1.4143)1 algorithm presented in [E. Prieto, The method of extremal structure on the k-maximum cut problem, in: The Proceedings of Computing: The Australasian Theory Symposium (CATS), 2005, pp. 119-126];
- (iv)
- an O∗(n2) algorithm for optimization version of MAXDAG in directed graphs. This is the first such algorithm to the best of our knowledge;
- (v)
- an O∗(k2) parameterized algorithm for MAXDAG in directed graphs. This improves the previous best of O∗(k4) presented in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458];
- (vi)
- an O∗(k16) parameterized algorithm to determine whether an oriented graph having m arcs has an acyclic subgraph with at least m/2+k arcs. This improves the O∗(k2) algorithm given in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458].
16.
Juan Liu 《Information Processing Letters》2008,108(3):90-93
We study the super-connected, hyper-connected and super-arc-connected Cartesian product of digraphs. The following two main results will be obtained:
- (i)
- If δ+(Di)=δ−(Di)=δ(Di)=κ(Di) for i=1,2, then D1×D2 is super-κ if and only if ,
- (ii)
- If δ+(Di)=δ−(Di)=δ(Di)=λ(Di) for i=1,2, then D1×D2 is super-λ if and only if ,
17.
David R. Stoutemyer 《Journal of Symbolic Computation》2011,46(7):859-887
This article provides goals for the design and improvement of default computer algebra expression simplification. These goals can also help users recognize and partially circumvent some limitations of their current computer algebra systems. Although motivated by computer algebra, many of the goals are also applicable to manual simplification, indicating what transformations are necessary and sufficient for good simplification when no particular canonical result form is required.After motivating the ten goals, the article then explains how the Altran partially factored form for rational expressions was extended for Derive and for the computer algebra in Texas Instruments products to help fulfill these goals. In contrast to the distributed Altran representation, this recursive partially factored semi-fraction form:
- •
- does not unnecessarily force common denominators,
- •
- discovers and preserves significantly more factors,
- •
- can represent general expressions, and
- •
- can produce an entire spectrum from fully factored over a common denominator through complete multivariate partial fractions, including a dense subset of all intermediate forms.
18.
19.
Len Bass Author Vitae Robert Nord Author Vitae Author Vitae David Zubrow Author Vitae Author Vitae 《Journal of Systems and Software》2008,81(9):1443-1455
The output of 18 software architecture evaluations is analyzed. The goal of the analysis is to find patterns in the important quality attributes and risk themes identified in the evaluations. The major results are
- •
- A categorization of risk themes.
- •
- The observation that twice as many risk themes are risks of “omission” as are risks of “commission”.
- •
- A failure to find a relationship between the business and mission goals of a system and the risk themes from an evaluation of that system.
- •
- A failure to find a correlation between the domain of a system being evaluated and the important quality attributes for that system.
- •
- A wide diversity of names used for various quality attributes.
20.
J. Dobaczewski W. Satu?a J. Engel P. Powa?owski J. Sarich A. Staszczak M. Stoitsov M. Zalewski 《Computer Physics Communications》2009,180(11):2361-2391