一类非线性递推的变距二分算法.doc

本文由xs5p6p99jy贡献 pdf文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。 第 卷（ 第 ） 期 汁算机与数字工程 一 类非线性递推 的变距二分算法 李 薇 张 建军 纪祥 鲲 武汉 ） （ 军工 程大学理学院 海 摘 要 提 出了一种有效求解 一类 非线性递推问题的并行算 法 。比较求 解此类 问题的奇偶二 分法 ， 变距 二分算法 显 非线性 递推 二 分算 法 著节省了总运算量 ； 比较约简二分法 ， 变距二分算法仅含消元过程 ， 算法结构简单 。 关键词 中图 分 类 号 （ ） ， ， ， ， ， 引言 众所周 知 ， 推 问题 的 算法 是 算 法研 究 的 递 ， ，一 ， ， （ ，） ： ： （ ） ， ： 其 中 ， 是给 定 的 常数 ， 是 满 足下 和 ，和 基础 ， 文献 提出 了求解一阶线性递推 的递归 倍增法 ， 文献 在研究 一类连续运算 的并行 算 法 基 础 上 提 出 了求 解 一 阶 线 性 递 推 的 一 算 列条件的函数 ： 条件 是可结 合 的 ： 厂 （ ） ， ， 。 ， （ ） ） ） ， 法， 文献 出 了计算 阶线 性 递归 方 程 提 组的并行算法 ， 文献 在此基础上提 出了一种 对齐算法 ， 文献 进一步提 出了计算 阶线性 递 归 方 程 组 的一 种 新 方 法 。非 线 性 递 推 的 并 行算法研究 较线 性 递推 复 杂 ， 于本 文 研究 的 对 一 条件 对是可分配的： ） （ （ ，（ ） （ ，） ， ，），） 条件 是半结合的， 即存在 函数 使得 ， ） （ （ ，） （ ， （ ，） ， ） ： 下面 ， 我们 推导它 的变距 二分算 法 。 类非线性递推问题 ， 文献 出了求 解它 的 提 不失一般性 ， ， 设 ， 利用上述条件 ， 我们有 奇偶二分法 和 约 简二分 法 ， 奇偶 二分 法 计算 量 较 大 ， 约 简 二 分 法 含 约 简 过 程 和 回代 过 程 ， 而 算 法结构 复杂 。本 文提 出 的变 距二 分算 法 ， 不仅 显著节 省了总运算量 ， 而且算 法结构简单 ， 并行 性能好 。 ， （ ） ， ， 利 【 （ ， ） ， 用 条件 有 ， （， ） ） 一类非线性递推 的变距二分 算法 考 虑如 非线性 递 推问题 ： ， （ ， ，（ ， ） ） （ ： （ ） ） ， ， （ ） （ ， ， 厂 ： （ ： ， （ （ ， ， ） ） ） 收到本文时 间： 年 月 日 一类非线性递推的变距二 分算 法 ： 第 卷 再 利用 条件 得 （ 口 ） ， ） ） ， 口 （ ， ） ， （ ，（ ） ， 一 ） ， 一一 （ ） （ ） ） （ ） ， ；） 一 一 最后利用条件 得出 （ ） ，（ （ ， ） ， （ ） ） ） ， 一 一 ， ” 日 令 ： （ ， ， ， ， ， 一， ） ） 【 （ ） ， 则有 特例分析 我们来看一个例子 ： 中 ， 在（ ） 取 ，） ， 这样定义 的函数满足条 （ ，） ，（ ，） 件 这样递推问题 （ ） ， ， 可写成 ： ，（ ， ） ， ， ：） ： ， 一 这样加工得出的递推关 系与原递推关系具有 相同的形式 ， 只是步长为 同理可以加工步长为 ， 的递 推公 式 ， 工 加 次 即可 获得 所 求解。 ：（ ， ， ） ） 设 上 面推 导 的问 题 （ ） 由 的变 距二 分 这样 ， 我们可以写出非线性递推问题 （ ） 的变 距二分算法如下 ： 第 ： ， 的倍数 分类 ， 公式 步 将 按 按 计算 算法 ， 快 可 以 写 出递 推 问题 （ ） 很 的变 距 二分 算法。 算法如下 ： ， ， 对 （ ） ） ， 计算 一 ， ， ， 。 一 二 二 ： ，： ） （） ， ， 一 ， ， ， ： 。 ，一， ， ：， ， 第 步 ： ， 按 将 的倍数分 类 ， 按公 式 计算 （ ） （ ） ） （ 二 ：， ， 一 （ ， ） （： ） ： ： 结果 ： （： ，） ；： ； 卫 ， ， ， ， ， ， 一 ： 一， ， ， ， ， 上述算法在 方向串行 ， ，方向并行计算。 （ ， ， ） （ ） 假设处理机台数 并且设乘法运行时间 ， 为 丁， 指数运算运行时间为 ， 则我们 可以对上述 变距二分算法进行效能分析 ： 运行 时间 ： （ ） ） 一 一 ， 卫 ， 卫） ：。 ：） （ ） 一 ， ， ：， ：， ： 鲁 第 ： ， 步 将 按 的倍数分 类 ， 公 式 按 串行计算问题（ ） 所需时间：帛 （ ） 二分法加龇 计算 一 ） （ ） （ ） 叶 二分法效率： 岫 ， ， 一 “ 二 ， 一 下面列出此算法与奇偶二分法 、 约简二分法的 加速比和效率比较 （ 丁 盯 ： 设 ： ， ） ， （ 下转 第 页） 第 （ 第 卷 ） 期 计算机与数字 程 二 配 置表 中 ， 没有 是 子句 的 语句 。它 特 性 。该 映射 机 制 对 于 有 行 业 共 享 标 准 的 电 子 在应用加入交换系统时设定 ， 与应用系统的数据库 资源相对应。在执行应用关系数据向 文档转 换时， 根据 请 求 文档 头 部 的 资 源标 识 选 择 要 政务系统都可适用 。在交换 网关 中实现了 消息 的路 由， 由算法 通过 给 文档 包装 头 路 部信息实现 ， 交换系统有统 的交换格式 使 提 高了模块的通用性 。本地 通讯 接 口与交换 网关 之 间使用 与 相 结 合 的技术 实现 消息 的异步安全传输 ， 保证 了原 型 系统 消息 的 安全可靠传输 。 该原型系统设计 目前仅考虑 了传输 的基本需 求， 作为一个完整 的数据交换系统， 还有待于将数 据的传输备份、 交换过程监控管理 、 交换 日志等模 执行 的 语句 ， 加上请求文档 中 子句构 成一个完整的请求 ， 在数据库中执行该请求可得到 满足共享规范的 文档。 映 射 子句 生 毫 映 图 扩 展 模 板 驱 动 模型 块考 虑其 中 。 参 考 文 献 总结 电子政务交换原型系统采用星形树 网络交换 结构 ， 与行业 内物理网络架构一致同时反映交换管 理权限控制的区域分级特点。原型系统在星形树 交换结构的基础上按功能归属分为本地通讯接 口 和交换网关两个部分。本地通讯接 口封装 了 朱勤 陆建新 陈 继红 基于 的异 构数据 交换 技术及其 实现 计算机应用与软件 ， 中凯 李 与 双 向数 据转换 接 口的设计 计算机与现代化 ， ） （ ： ， ， ， ， ， ： ： ， ， ， ， 文档与关系数据库 的映射功能和 文档收 发 处理功能。 文档与关 系数据库的映射扩展了 基于模板驱动的映射， 充分利用 了行业数据的共享 胡朝 晖， 基于 的数据库总体分析 出乖 出毋出乖出 乖出 （ 接第 上 页 ） 表 变距 、 奇偶 、 约简算法加速比和效率 比较 变距 二分算法显著节省了总运算量 ， 比较约简二分法 ， 变距二分算法仅含消元过程， 算法结构简单。不足之 处是当较大时 ， 此算法需要的处理机台数也较大。当 处理机台数不够时， 可以采用分段技术。 参 考 文 献 ， ， 一 ： ， （ ） 从表中可 以看到 ， 当处理机台数 时 ， 变 崔国华 ， 洪帆 ， 鹏军 ， 珊 柳 计算 一类连续运 算 的有效 并 距二分算法的加速 比和效率都是最高 的。更重要 行算法 华 中理工大学学报 （ ） 的是 当处理机 台数有限时 ， 变距二分算法由于总运 张德富 ， 盛蓝 计算 序线性递归 方程组 的一种有效 算量少 ， 其效率明显高于奇偶二分法。 并行方法 计算机学报 ， （ ） ， ： 算法小结 的前 提下反复加工所给递推公式 ， 在加工 过程 中充分