• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Mathematical foundations of computer science 2010 >Evaluating Non-square Sparse Bilinear Forms on Multiple Vector Pairs in the I/O-Model
【24h】

Evaluating Non-square Sparse Bilinear Forms on Multiple Vector Pairs in the I/O-Model

机译：在I / O模型中评估多个向量对上的非平方稀疏双线性形式

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider evaluating one bilinear form defined by a sparse N_y x N_x matrix A having h entries on w pairs of vectors The model of computation is the semiring I/O-model with main memory size M and block size B. For a range of low densities (small h), we determine the I/O-complexity of this task for all meaningful choices of N_x, N_y, w, M and B, as long as M > B~2 (tall cache assumption). To this end, we present asymptotically optimal algorithms and matching lower bounds. Moreover, we show that multiplying the matrix A with w vectors has the same worst-case I/O-complexity.
机译：我们考虑评估由稀疏的N_y x N_x矩阵A定义的一种双线性形式，该矩阵A在w对向量上具有h个条目。计算模型是具有主存储器大小M和块大小B的半环I / O模型。密度（小h），只要M> B〜2（高缓存假设），我们就为N_x，N_y，w，M和B的所有有意义的选择确定此任务的I / O复杂度。为此，我们提出了渐近最优算法和匹配的下界。此外，我们表明将矩阵A与w向量相乘具有相同的最坏情况I / O复杂度。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号