一類(lèi)非線性遞推的變距二分算法

1、 本文由xs5p6p99jy貢獻(xiàn) pdf文檔可能在WAP端瀏覽體驗(yàn)不佳。建議您優(yōu)先選擇TXT，或下載源文件到本機(jī)查看。 第 卷（ 第 ） 期 汁算機(jī)與數(shù)字工程 一 類(lèi)非線性遞推 的變距二分算法 李 薇 張 建軍 紀(jì)祥 鯤 武漢 ） （ 軍工 程大學(xué)理學(xué)院 海 摘 要 提 出了一種有效求解 一類(lèi) 非線性遞推問(wèn)題的并行算 法 。比較求 解此類(lèi) 問(wèn)題的奇偶二 分法 ， 變距 二分算法 顯 非線性 遞推 二 分算 法 著節(jié)省了總運(yùn)算量 ； 比較約簡(jiǎn)二分法 ， 變距二分算法僅含消元過(guò)程 ， 算法結(jié)構(gòu)簡(jiǎn)單 。 關(guān)鍵詞 中圖 分 類(lèi) 號(hào) （ ） ， ， ， ， ， 引言 眾所周 知 ， 推 問(wèn)題 的 算法

2、是 算 法研 究 的 遞 ， ，一 ， ， （ ，） ： ： （ ） ， ： 其 中 ， 是給 定 的 常數(shù) ， 是 滿(mǎn) 足下 和 ，和 基礎(chǔ) ， 文獻(xiàn) 提出 了求解一階線性遞推 的遞歸 倍增法 ， 文獻(xiàn) 在研究 一類(lèi)連續(xù)運(yùn)算 的并行 算 法 基 礎(chǔ) 上 提 出 了求 解 一 階 線 性 遞 推 的 一 算 列條件的函數(shù) ： 條件 是可結(jié) 合 的 ： 廠 （ ） ， ， 。 ， （ ） ） ） ， 法， 文獻(xiàn) 出 了計(jì)算 階線 性 遞歸 方 程 提 組的并行算法 ， 文獻(xiàn) 在此基礎(chǔ)上提 出了一種 對(duì)齊算法 ， 文獻(xiàn) 進(jìn)一步提 出了計(jì)算 階線性 遞 歸 方 程 組 的一 種 新 方 法 。非 線

3、 性 遞 推 的 并 行算法研究 較線 性 遞推 復(fù) 雜 ， 于本 文 研究 的 對(duì) 一 條件 對(duì)是可分配的： ） （ （ ，（ ） （ ，） ， ，），） 條件 是半結(jié)合的， 即存在 函數(shù) 使得 ， ） （ （ ，） （ ， （ ，） ， ） ： 下面 ， 我們 推導(dǎo)它 的變距 二分算 法 。 類(lèi)非線性遞推問(wèn)題 ， 文獻(xiàn) 出了求 解它 的 提 不失一般性 ， ， 設(shè) ， 利用上述條件 ， 我們有 奇偶二分法 和 約 簡(jiǎn)二分 法 ， 奇偶 二分 法 計(jì)算 量 較 大 ， 約 簡(jiǎn) 二 分 法 含 約 簡(jiǎn) 過(guò) 程 和 回代 過(guò) 程 ， 而 算 法結(jié)構(gòu) 復(fù)雜 。本 文提 出 的變 距二 分算 法 ，

4、 不僅 顯著節(jié) 省了總運(yùn)算量 ， 而且算 法結(jié)構(gòu)簡(jiǎn)單 ， 并行 性能好 。 ， （ ） ， ， 利 【 （ ， ） ， 用 條件 有 ， （， ） ） 一類(lèi)非線性遞推 的變距二分 算法 考 慮如 非線性 遞 推問(wèn)題 ： ， （ ， ，（ ， ） ） （ ： （ ） ） ， ， （ ） （ ， ， 廠 ： （ ： ， （ （ ， ， ） ） ） 收到本文時(shí) 間： 年 月 日 一類(lèi)非線性遞推的變距二 分算 法 ： 第 卷 再 利用 條件 得 （ 口 ） ， ） ） ， 口 （ ， ） ， （ ，（ ） ， 一 ） ， 一一 （ ） （ ） ） （ ） ， ；） 一 一 最后利用條件 得出 （ ）

5、，（ （ ， ） ， （ ） ） ） ， 一 一 ， ” 日 令 ： （ ， ， ， ， ， 一， ） ） 【 （ ） ， 則有 特例分析 我們來(lái)看一個(gè)例子 ： 中 ， 在（ ） 取 ，） ， 這樣定義 的函數(shù)滿(mǎn)足條 （ ，） ，（ ，） 件 這樣遞推問(wèn)題 （ ） ， ， 可寫(xiě)成 ： ，（ ， ） ， ， ：） ： ， 一 這樣加工得出的遞推關(guān) 系與原遞推關(guān)系具有 相同的形式 ， 只是步長(zhǎng)為 同理可以加工步長(zhǎng)為 ， 的遞 推公 式 ， 工 加 次 即可 獲得 所 求解。 ：（ ， ， ） ） 設(shè) 上 面推 導(dǎo) 的問(wèn) 題 （ ） 由 的變 距二 分 這樣 ， 我們可以寫(xiě)出非線性遞推問(wèn)題 （ ）

6、的變 距二分算法如下 ： 第 ： ， 的倍數(shù) 分類(lèi) ， 公式 步 將 按 按 計(jì)算 算法 ， 快 可 以 寫(xiě) 出遞 推 問(wèn)題 （ ） 很 的變 距 二分 算法。 算法如下 ： ， ， 對(duì) （ ） ） ， 計(jì)算 一 ， ， ， 。 一 二 二 ： ，： ） （） ， ， 一 ， ， ， ： 。 ，一， ， ：， ， 第 步 ： ， 按 將 的倍數(shù)分 類(lèi) ， 按公 式 計(jì)算 （ ） （ ） ） （ 二 ：， ， 一 （ ， ） （： ） ： ： 結(jié)果 ： （： ，） ；： ； 衛(wèi) ， ， ， ， ， ， 一 ： 一， ， ， ， ， 上述算法在 方向串行 ， ，方向并行計(jì)算。 （ ， ， ） （

7、） 假設(shè)處理機(jī)臺(tái)數(shù) 并且設(shè)乘法運(yùn)行時(shí)間 ， 為 丁， 指數(shù)運(yùn)算運(yùn)行時(shí)間為 ， 則我們 可以對(duì)上述 變距二分算法進(jìn)行效能分析 ： 運(yùn)行 時(shí)間 ： （ ） ） 一 一 ， 衛(wèi) ， 衛(wèi)） ：。 ：） （ ） 一 ， ， ：， ：， ： 魯 第 ： ， 步 將 按 的倍數(shù)分 類(lèi) ， 公 式 按 串行計(jì)算問(wèn)題（ ） 所需時(shí)間：帛 （ ） 二分法加齜 計(jì)算 一 ） （ ） （ ） 葉 二分法效率： 岫 ， ， 一 “ 二 ， 一 下面列出此算法與奇偶二分法 、 約簡(jiǎn)二分法的 加速比和效率比較 （ 丁 盯 ： 設(shè) ： ， ） ， （ 下轉(zhuǎn) 第 頁(yè)） 第 （ 第 卷 ） 期 計(jì)算機(jī)與數(shù)字 程 二 配 置表 中

8、 ， 沒(méi)有 是 子句 的 語(yǔ)句 。它 特 性 。該 映射 機(jī) 制 對(duì) 于 有 行 業(yè) 共 享 標(biāo) 準(zhǔn) 的 電 子 在應(yīng)用加入交換系統(tǒng)時(shí)設(shè)定 ， 與應(yīng)用系統(tǒng)的數(shù)據(jù)庫(kù) 資源相對(duì)應(yīng)。在執(zhí)行應(yīng)用關(guān)系數(shù)據(jù)向 文檔轉(zhuǎn) 換時(shí)， 根據(jù) 請(qǐng) 求 文檔 頭 部 的 資 源標(biāo) 識(shí) 選 擇 要 政務(wù)系統(tǒng)都可適用 。在交換 網(wǎng)關(guān) 中實(shí)現(xiàn)了 消息 的路 由， 由算法 通過(guò) 給 文檔 包裝 頭 路 部信息實(shí)現(xiàn) ， 交換系統(tǒng)有統(tǒng) 的交換格式 使 提 高了模塊的通用性 。本地 通訊 接 口與交換 網(wǎng)關(guān) 之 間使用 與 相 結(jié) 合 的技術(shù) 實(shí)現(xiàn) 消息 的異步安全傳輸 ， 保證 了原 型 系統(tǒng) 消息 的 安全可靠傳輸 。 該原型系

9、統(tǒng)設(shè)計(jì) 目前僅考慮 了傳輸 的基本需 求， 作為一個(gè)完整 的數(shù)據(jù)交換系統(tǒng)， 還有待于將數(shù) 據(jù)的傳輸備份、 交換過(guò)程監(jiān)控管理 、 交換 日志等模 執(zhí)行 的 語(yǔ)句 ， 加上請(qǐng)求文檔 中 子句構(gòu) 成一個(gè)完整的請(qǐng)求 ， 在數(shù)據(jù)庫(kù)中執(zhí)行該請(qǐng)求可得到 滿(mǎn)足共享規(guī)范的 文檔。 映 射 子句 生 毫 映 圖 擴(kuò) 展 模 板 驅(qū) 動(dòng) 模型 塊考 慮其 中 。 參 考 文 獻(xiàn) 總結(jié) 電子政務(wù)交換原型系統(tǒng)采用星形樹(shù) 網(wǎng)絡(luò)交換 結(jié)構(gòu) ， 與行業(yè) 內(nèi)物理網(wǎng)絡(luò)架構(gòu)一致同時(shí)反映交換管 理權(quán)限控制的區(qū)域分級(jí)特點(diǎn)。原型系統(tǒng)在星形樹(shù) 交換結(jié)構(gòu)的基礎(chǔ)上按功能歸屬分為本地通訊接 口 和交換網(wǎng)關(guān)兩個(gè)部分。本地通訊接 口封裝 了 朱勤

10、陸建新 陳 繼紅 基于 的異 構(gòu)數(shù)據(jù) 交換 技術(shù)及其 實(shí)現(xiàn) 計(jì)算機(jī)應(yīng)用與軟件 ， 中凱 李 與 雙 向數(shù) 據(jù)轉(zhuǎn)換 接 口的設(shè)計(jì) 計(jì)算機(jī)與現(xiàn)代化 ， ） （ ： ， ， ， ， ， ： ： ， ， ， ， 文檔與關(guān)系數(shù)據(jù)庫(kù) 的映射功能和 文檔收 發(fā) 處理功能。 文檔與關(guān) 系數(shù)據(jù)庫(kù)的映射擴(kuò)展了 基于模板驅(qū)動(dòng)的映射， 充分利用 了行業(yè)數(shù)據(jù)的共享 胡朝 暉， 基于 的數(shù)據(jù)庫(kù)總體分析 出乖 出毋出乖出 乖出 （ 接第 上 頁(yè) ） 表 變距 、 奇偶 、 約簡(jiǎn)算法加速比和效率 比較 變距 二分算法顯著節(jié)省了總運(yùn)算量 ， 比較約簡(jiǎn)二分法 ， 變距二分算法僅含消元過(guò)程， 算法結(jié)構(gòu)簡(jiǎn)單。不足之 處是當(dāng)較大時(shí) ， 此算法需要的處理機(jī)臺(tái)數(shù)也較大。當(dāng) 處理機(jī)臺(tái)數(shù)不夠時(shí)， 可以采用分段技術(shù)。 參 考 文 獻(xiàn) ， ， 一 ： ， （ ） 從表中可 以看到 ， 當(dāng)處理機(jī)臺(tái)數(shù) 時(shí) ， 變 崔國(guó)華 ， 洪帆 ， 鵬軍 ， 珊 柳 計(jì)算 一類(lèi)連續(xù)運(yùn) 算 的有效 并 距二分算法的加速 比和效率都是最高 的。更重要 行算法 華 中理工大學(xué)學(xué)報(bào) （ ） 的是 當(dāng)處理機(jī) 臺(tái)數(shù)有限時(shí) ， 變距二分算法由于總運(yùn) 張德富 ， 盛藍(lán) 計(jì)算 序線性遞歸 方程組 的一種有效 算量少 ， 其效率明顯高于奇偶二分法。 并行方法 計(jì)算機(jī)學(xué)報(bào) ， （ ） ， ： 算法小結(jié) 的前 提下反復(fù)加工所給遞推公式 ， 在加工 過(guò)程 中充分