交错符号矩阵数的界

满足性质A1.所有元素都等于 1、-1或0;A2.每行、每列元素之和都等于 1;A3.每行、每列非零元素的符号交替变化的 n 阶方阵称为 n 阶交错符号矩阵,其全体记为 A_n,A_n=|A_n|为 n 阶交错符号矩阵的数目。通过计算已经验证:当1≤n≤10时,     

奇异值分解法在预测用户页面兴趣度中的应用

如何挖掘用户感兴趣的内容并向其推荐相应的产品是许多商务网站关注的重点。本文提出一个用户页面兴趣度公式,据此得到一个稀疏的页面兴趣度矩阵,考虑到矩阵的稀疏性会影响预测的准确性,我们首先用稀疏矩阵中每列非零元素的平均值对该列中值为零的元素进行修正,然后用奇异值分解法对原稀疏矩阵中值为零的元素进行再次修正,进而根据修正后的矩阵用SlopeOne算法对用户的页面兴趣度进行预测并用某网站的数据验证。结果表明:与稀疏矩阵相比,用修正后的矩阵预测的准确性有较大提高。     

图论在稀疏对称矩阵中的应用

本文简要叙述图论的基本概念及其与对称矩阵的关系,并建立对称正定矩阵的Cholesky分解及其相应的消去图、商图间的关系。利用所建立的关系为矩阵找到一个好的“排序”,使得它的Cholesky分解的下三角矩阵有较少的非零元素。同时应用可达集的概念确定新产生非零元素的位置和个数.并给出相应的实现方法和数值试验结果。     

混合边界条件下的三维定常 旋转Navier-Stokes方程的原始变量有限元计算

本文利用原始变量有限元法求解混合边界条件下的三维定常旋转Navier-Stokes方程,证明了离散问题解的存在唯一性,得到了有限元解的最优误差估计.给出了求解原始变量有限元逼近解的简单迭代算法,并证明了算法的收敛性.针对三维情况下计算资源的限制,采用压缩的行存储格式存储刚度矩阵的非零元素,并利用不完全的LU分解作预处理的GMRES方法求解线性方程组.最后分析了简单迭代和牛顿迭代的优劣对比,数值算例表明在同样精度下简单迭代更节约计算时间.     

具有完全并行度的SOR算法

1　引　　言Jacobi和 SOR迭代是求解线性方程组的两类基本的迭代方法 .并行计算机的出现使人们能立刻注意到它们在拥有并行处理性能上的显著差别 .Jacobi迭代因其各个分量的修正相互独立而具有十分明显的内在并行计算特性 .SOR则完全不同 ,其中诸分量的计算是逐个相关的 .由此而导致一般认为 SOR不适合并行处理 ,其内在并行性远不如 Jacobi迭代[1 ] [2 ] .由于 SOR多用于有限差分或有限元方法导致的大型稀疏方程组求解 ,因此 ,利用系数矩阵零元素或非零元素的特殊分布 ,采用红 -黑或多色排序成为实现 SOR并行处理的有效途径 .然而 ,…     

有限元的快速高精度算法

有限元方法已广泛运用到各个领域.然而,这种方法也有它的弊病,即,如欲获得高精度,则存贮量和计算量特别地大.超收敛和外推理论能较好地解决这一问题,即可在不增加计算量和存贮量的条件下,大大提高计算精度.但是外推和超收敛理论也有弊病,外推一般只适应于线性元,最好精度为O(h~4);超收敛性结果虽好,仍然不能减少计算量和存贮量.本文提供一种新方法,可将未知数个数(结点个数)压低到最低限度,但能达到高次元的超收敛精度.     

轴对称弹性体的有限元分析

轴对称弹性力学问题的有限元分析长期以来都是采用三角圆环有限元和线性形状函数.由于积分困难,常用近似积分求得刚度矩阵,这种近似积分对于靠近旋转对称轴的元素,误差很大,所以,长期以来,被认为不满意的办法.也有用精确积分计算刚度矩阵的.但本文指出,这种积分只适用于有中孔的轴对称体.对于实心的轴对称体而言,这种刚度矩阵都不收敛,计算是无效的.本文提出了一种新的形状函数,当径向座标r接近于零时,这种形状函数的径向位移u自然地接近于零.如果用这种新的形状函数,则由此计算求得的刚度矩阵,不论三角圆环有限元的位置是否靠近轴线.都是存在的.这种有限元,就能用于计算实心的轴对称体的问题.     

混合有限元非嵌套网格型预处理法

1 引言 众所周知,二阶椭圆型问题混合有限元离散以后的矩阵是不定的,所以对混合法很难形成一种有效的区域分解法,在文[9]、[10]、[11]中提出了一些混合有限元方法的区域分解法,但在实际计算中有很多局限性。最近Chen对混合有限元法提出一种全新的解释并把它应用到多重网格法中,他的基本思想是混合有限元离散的代数系统实际上等价于某个非协调有限元离散的代数系统,这样可把一个不定问题转化为一个正定问题,本文将基于这种思想考虑混合有限元的区域分解法。 若按传统的Dryia-widlund两水平加性Schwarz方法,要求两层网格间具有嵌套关系,这样在应用中将带来很大的不便。本文将不要求粗网格嵌入细网格中,减少两层网格间的     

一类可逆矩阵逆矩阵的图论解法

设 M( G)是简单无向图 G的关联矩阵 ,A是 M( G)的可逆子矩阵 ,γ( A)是逆矩阵 A- 1中非零元素的个数 .获得了求逆矩阵 A- 1的一种图论方法 ,并且得到了γ( A)的精确上下界以及达到上下界时子矩阵 A的图论刻划     

求线性规划问题相容方程组非负解的算法

本文提出一个解线性规划问题的新算法.其最优解是通过求一个相容方程组的非负解而得到.这算法的计算量在最坏情况下是O(mnτ),其中τ是相应方程的m×n矩阵非零元素的个数.     

部分联合运输策略下的物流车辆路径优化问题研究

论文分析了物流车辆路径优化问题的特点,提出了企业自营物流和第三方物流协同运输的部分联合运输策略。根据客户需求节点的特点进行了节点分类,建立了以车辆调用成本、车辆运输成本、第三方物流运输成本之和最小为目标的整数线性规划模型。根据部分联合运输策略下各类客户需求点运输方式特点,构造了一种新的变维数矩阵编码结构,并对传统算法中概率选择操作方式进行修改,提出了一种新的智能优化算法并与枚举法和遗传算法的运算结果进行了算法性能对比分析。结果显示,本文提出的逆选择操作蚁群算法具有较快的运算速度和较高的稳定性,是求解此类问题的一种有效算法。     

����ά�DZ���Jackson����ļ�����Ϊ

??For the infinite Jackson network, assume that the net input rates are greater than the service rates for some nodes. Via solving the new throughput equation, the stochastic comparable processes are obtained by coupling method, and furthermore the limits for the queueing length in all nodes are also obtained. Despite the whole network is non-ergodic, it is possible to get the maximal ergodic subnetwork.     

A robust optimization approach for multicast network coding under uncertain link costs

Network coding is a technique that can be used to improve the performance of communication networks by performing mathematical operations at intermediate nodes. An important problem in coding theory is that of finding an optimal coding subgraph for delivering network data from a source node throughout intermediate nodes to a set of destination nodes with the minimum transmission cost. However, in many real applications, it can be difficult to determine exact values or specific probability distributions of link costs. Establishing minimum-cost multicast connections based on erroneous link costs might exhibit poor performance when implemented. This paper considers the problem of minimum-cost multicast using network coding under uncertain link costs. We propose a robust optimization approach to obtain solutions that protect the system against the worst-case value of the uncertainty in a prespecified set. The simulation results show that a robust solution provides significant improvement in worst-case performance while incurring a small loss in optimality for specific instances of the uncertainty.     

基于奇偶校验的Petri网控制器的故障检测

提出基于奇偶校验的方法对Petri网控制器进行故障检测.设计出满足包含标识向量和Parikh向量的线性约束的Petri网控制器;建立一个包含一定数量库所的附加Petri网控制器以满足奇偶校验的编码要求;分别针对库所故障和变迁故障,选用不同的奇偶校验参数进行故障检测,并通过实例详细阐明了故障检测的过程.     

Conflict analysis in mixed integer programming

Conflict analysis for infeasible subproblems is one of the key ingredients in modern SAT solvers. In contrast, it is common practice for today’s mixed integer programming solvers to discard infeasible subproblems and the information they reveal. In this paper, we try to remedy this situation by generalizing SAT infeasibility analysis to mixed integer programming.We present heuristics for branch-and-cut solvers to generate valid inequalities from the current infeasible subproblem and the associated branching information. SAT techniques can then be used to strengthen the resulting constraints. Extensive computational experiments show the potential of our method. Conflict analysis greatly improves the performance on particular models, while it does not interfere with the solving process on the other instances. In total, the number of required branching nodes on general MIP instances was reduced by 18% in the geometric mean, and the solving time was reduced by 11%. On infeasible MIPs arising in the context of chip verification and on a model for a particular combinatorial game, the number of nodes was reduced by 80%, thereby reducing the solving time by 50%.     

An efficient coding methods for the two composition types of the Korean alphabet on a MasPar machine

There are two types of composition systems for the Korean alphabet: a combined system and a composite system. This paper describes an efficient coding method for both of these two types. Using this coding method, with the combined system yields about 10.5% code-length savings per a Korean character, while it yields about 45% savings with the composite system. In other words, the coding method produces a better result (i.e. 34.5% better) with the composite system than with the combined system. The simulation has been performed on a MasPar machine having 64 processors. The results show that the combined system achieved a 45.851-fold speedup while the composite system achieved a 47.274-fold speedup.     

A Parallel Interior Point Method and Its Application to Facility Location Problems

We present a parallel interior point algorithm to solve block structured linear programs. This algorithm can solve block diagonal linear programs with both side constraints (common rows) and side variables (common columns). The performance of the algorithm is investigated on uncapacitated, capacitated and stochastic facility location problems. The facility location problems are formulated as mixed integer linear programs. Each subproblem of the branch and bound phase of the MIP is solved using the parallel interior point method. We compare the total time taken by the parallel interior point method with the simplex method to solve the complete problems, as well as the various costs of reoptimisation of the non-root nodes of the branch and bound. Computational results on two parallel computers (Fujitsu AP1000 and IBM SP2) are also presented in this paper.     

Linear Approximations in a Dynamic Programming Approach for the Uncapacitated Single-Source Minimum Concave Cost Network Flow Problem in Acyclic Networks

We consider minimum concave cost flow problems in acyclic, uncapacitated networks with a single source. For these problems a dynamic programming scheme is developed. It is shown that the concave cost functions on the arcs can be approximated by linear functions. Thus the considered problem can be solved by a series of linear programs. This approximation method, whose convergence is shown, works particularly well, if the nodes of the network have small degrees. Computational results on several classes of networks are reported.     

An Efficient Genetic Algorithm for the p-Median Problem

We propose a new genetic algorithm for a well-known facility location problem. The algorithm is relatively simple and it generates good solutions quickly. Evolution is facilitated by a greedy heuristic. Computational tests with a total of 80 problems from four different sources with 100 to 1,000 nodes indicate that the best solution generated by the algorithm is within 0.1% of the optimum for 85% of the problems. The coding effort and the computational effort required are minimal, making the algorithm a good choice for practical applications requiring quick solutions, or for upper-bound generation to speed up optimal algorithms.     

求解瞬时温度场的有限元显式算法

在一公共节点为中心的各单元中,对于线性形函数,实际计算和数字实验表明,温度在单元各节点上的时间导数用它在中心节点上的时间导数表示是可取和合理的。由此可在对微分方程用有限元法进行空间离散的基础上得到单个节点温度的时间导数与其周围节点温度的关系,建立温度场的显式计算格式。它具有计算简捷的特点。用最大值原理对稳定性的分析导出了与稳式算法类似的稳定性条件。