关键词： Piecewise algebraic curve   Multivariate spline   Truncated sign   Groebner bases   Interval arithmetic  

摘要： Piecewise algebraic curve is defined as the zero set of a bivariate spline. In this paper, we mainly study the intersection points algorithm for two given piecewise algebraic curves based on Groebner bases. Given a domain D and a partition Delta, we present a flow and introduce the truncated signs, and then represent the two piecewise algebraic curves in the global form. We get their Groebner bases with respect to a lexicographic order and adopt the interval arithmetic in the back-substitution process, which makes the algorithm numerically precise. An example is also presented to show the algorithm's feasibility and effectiveness.

关键词： pattern recognition   estimation algorithm   matrices of estimates   correct algorithm   normalization   algebra over algorithms  

摘要： Algebra over estimation algorithms with addition, multiplication by a constant, and normalization operations is investigated. Normalization is interpreted as a linear (with respect to each row) transformation of the matrix of estimates that takes the maximum entry of the row to unity and the minimum entry to zero. The algebraic closure is described, a formula for its dimension is obtained, and correctness criteria are formulated.

关键词： Algorithms   Bulb drop   Dihedral angles   Geometry   Permutations  

摘要： Geometric Problems become increasingly intractable and difficult to visualize as the number of dimensions increases beyond three. Inductions from lower dimensional spaces are possible yet often awkward. This thesis shows how elementary linear algebra, vector calculus, and combinatorics offer improved methods for calculating the dihedral angles of n-simplicies and proving a generalization of the Pythagorean theorem directly. A large class of search problems are solved in O(log n) time with a traditional binary search. This thesis extends this to a class of problems where the cost of high guesses differs from the cost of low guesses. Weighted binary searches have broad applicability, and in particular, the bulb drop problem is extended, analyzed and solved. Modern Rubik cube research focuses on solving the cube as fast as possible using heavy machinery and computation. Speed cubists routinely memorize 115 different move sequences and practice relentlessly so that they might solve the cube in 15-20 seconds. Mathematicians apply abstract algebra to perform massively parallel computations in order to seek out the fastest way to solve the cube from any position. The diameter of the Rubik’s cube group remains undetermined as of this writing; recently, God’s Algorithm, the method of solving the cube in the fewest possible moves from a scrambled position, was given a least upper bound of 26 moves. This thesis considers the problem from the opposite end of the spectrum. What simple classes of move sequences exist that solve the cube? Since every position of the cube can be achieved by making quarter turns of the faces, quarter turns is a class of moves that solves the cube. It can also be shown that half turns is insufficient. This thesis shows that commutators of quarter turns suffices using methods that have applicability to other cube related problems. There are many ways that the permutation groups may be mapped onto the integers. Some of these maps have interesting prope

关键词： 均衡约束数学规划   SQP算法   线性互补约束   非线性互补约束   S-稳定点   全局收敛   超线性收敛  

摘要： 均衡约束数学规划是近年来数学规划领域发展起来的一个热点研究问题.它起源于对策论,并且在经济分析、自然科学和工程计算中有着广泛地应用.然而,这类问题的研究却非常复杂,最主要的困难在于它的可行域的复杂性,一些常用的约束规范条件对均衡约束数学规划问题来说一般都不成立,从而非线性规划一些经典的理论和算法一般不能直接应用到均衡问题上来.因此,如何将该类问题进行转化,给出研究该类问题的等价形式,并研究其最优性条件和算法就变得非常重要. 本文主要做了以下两方面工作: 首先基于逐步逼近心想,构造一个与原问题等价的光滑非线性规划.借助降维思想,在每步迭代时,主方向由定义在Rn+m上的QP子问题和一个方程组求得.为了克服Maratos效应,我们通过求解一个线性方和组得到二阶修正方向.在不需要上层严格互补的适当假设条件下,证明了算法的全局收敛性和超线性收敛性.当算法有限步终止时,当前迭代点为原问题的一个精确稳定点.数值实验表明算法的有效性. 其次利用归并函数,提出一个新的磨光方法,基于该方法,构造一个在求解意义上与原问题等价的磨光非线性规划.在每次迭代时,只需构造仅含等式约束的QP子问题来产生主方向,再通过一个显式公式来产生修正方向以克服Maratos效应,从而避免求解另一个QP子问题.在一些适当的假设条件下,提出的SQP算法全局收敛到原问题的S-稳定点,且算法的收敛速率是超线性的.数值实验验证了算法的有效性.

关键词： 有限元法   遗传算法   神经网络  

摘要： 数学算法在工程领域方面非常重要。介绍有限单元法,遗传算法和神经网络的研究现状,描述它的主要特点,基本原理和应用领域。

关键词： OpenMP   并行处理   腐蚀   膨胀   数学形态学  

摘要： 本文介绍了共享存储系统并行编程接口OpenMP模型、指令等。并通过研究数学形态学中的两种基本形态:腐蚀和膨胀,并利用腐蚀和膨胀算子进行空间关系的判断。

关键词： ontology   algebra of algorithms   designing and synthesis of programs   parallel programs  

摘要： An approach to formalized development of parallel programs using ontologies and algebraalgorithmic facilities is proposed. Ontology gives opportunity to describe the skeleton of the program representing main objects in the given subject domain, i.e. data, functions to process data and relations between functions. Once the skeleton of the program has been built, further development can be done in automated manner with the Integrated toolkit for Design and Synthesis (IDS) developed by the authors, which is based on using algorithmic algebras facilities. The application of the approach is illustrated with an example of developing parallel MPI program in the subject domain of sorting algorithms.

关键词： CONFERENCES & conventions   MATHEMATICAL analysis  

摘要： The article presents information on the symposium Computational Electronics: Physical Modeling, Mathematical Theory, and Numerical Algorithm.

关键词： 数学形态学   去噪算法   结构元素   Contourlet变换   并行化  

摘要： 图像去噪是图像处理中一种基本而重要的技术。图像在数字化的过程中不可避免地会引入一些噪声,这些噪声会妨碍人们对图像的理解,影响图像的质量。利用去噪技术可以从复杂的信号中提取出所需要的信号,并抑制干扰信号,使图像更加清晰,反映出的信息更准确。图像的清晰度主要决定于图像边缘、细线和小特征是否清晰,特征之间的区域变化是否平滑。传统的图像去噪方式,在去除噪声污染的同时会造成图像边缘的模糊,不能很好地保持轮廓信息。为了解决图像滤波时的轮廓保持问题,研究者们提出了一类新的非线性方法,即基于数学形态学的图像去噪方法。这种方法对图像形态特征进行分析,利用预先定义的结构元对信号进行匹配,以达到提取信号、抑制噪声的目的,具有并行性和快速性的特点,因而在国内外受到普遍关注。 本论文以数学形态学理论为基础,分别研究了二值图像、灰度图像、彩色图像的去噪算法,在传统的形态学去噪算法的基础上,进行改进和创新,进一步提高了图像的质量。 在二值图像去噪算法中,设计与实现了一种多结构元素的串行广义复合形态滤波器。由于传统的形态滤波只采用单一结构元素,致使滤波结果无法顾及图像在不同方向上的特征,不能完全滤除噪声,模糊了图像的细节特征。本文在二值图像去噪算法中采用了多尺度多方向的结构元素,不仅有效地抑制了图像中的噪声,而且较好地保持了图像的几何特征。同时利用广义复合形态滤波具有平移不变性、递增性、等幂性等重要特征进行图像降噪。在灰度图像去噪算法的设计上,采用了一种Contourlet变换结合Cycle Spinning技术、形态学HMT变换的去噪方法。Contourlet变换是一种真正的图像二维表示方法,具有多分辨性、局域性、方向性的优点,而Cycle Spinning技术能够有效抑制由于Contourlet变换缺乏平移不变性而引起的伪Gibbs现象,在以上两者结合的基础上,对于Contourlet分解后高频子带中的噪声,运用数学形态学中的HMT变换进行有针对性的提取和去除。与传统的小波变换阈值去噪方法相比,这种方法??的平滑了噪声,保持了更多的图像边缘和纹理细节,视觉效果也更好。 对于彩色图像去噪,采用了一种基于RGB彩色空间的改进的中值滤波,结合多结构元素的标量形态滤波算法。传统的中值滤波对所有的数据采用统一的处理方法,对每个像素都进行排序取中值,计算量巨大,时间复杂度高。而改进的中值滤波采用信噪分别处理的算法,排序时充分利用更新后的数据,克服了传统中值的不足,降低了时间复杂度,滤波效果也明显得到改善。同时根据人眼对三基色不同的敏感程度,选用不同大小的结构元素对三基色分别进行处理,与采用同样的结构元素对整个图像处理相比,在滤除噪声的同时,保留了更多的色彩信息,且不影响人眼对图像的视觉效果。本文在彩色图像去噪算法中,深入研究了改进的中值滤波算法并行化的可行性,实现了基于MPI的改进中值滤波的并行化算法,显著提高了改进的中值滤波算法的计算效率。 通过对各种改进算法的仿真实验效果和去噪算法性能指标(MAE、MSE、NMSE、PSNR)分析,表明本文各种改进算法比传统算法具有更大的灵活性,滤除噪声的能力显著增强,证实了算法的可行性和有效性。

关键词： nonbipartite matching   matroid intersection   algebraic algorithms   fast matrix multiplication  

摘要： We present new algebraic approaches for two well-known combinatorial problems: nonbipartite matching and matroid intersection. Our work yields new randomized algorithms that exceed or match the efficiency of existing algorithms. For nonbipartite matching, we obtain a simple, purely algebraic algorithm with running time O(n(omega)) where n is the number of vertices and omega is the matrix multiplication exponent. This resolves the central open problem of Mucha and Sankowski (2004). For matroid intersection, our algorithm has running time O(nr(omega-1)) for matroids with n elements and rank r that satisfy some natural conditions.